LLVM  14.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"
20 #include "llvm/IR/DIBuilder.h"
21 #include "llvm/IR/Mangler.h"
22 #include "llvm/IR/PassManager.h"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/Pass.h"
26 #include "llvm/Transforms/IPO.h"
27 #include <map>
28 #include <set>
29 #include <vector>
30 
31 #define DEBUG_TYPE "iroutliner"
32 
33 using namespace llvm;
34 using namespace IRSimilarity;
35 
36 // Set to true if the user wants the ir outliner to run on linkonceodr linkage
37 // functions. This is false by default because the linker can dedupe linkonceodr
38 // functions. Since the outliner is confined to a single module (modulo LTO),
39 // this is off by default. It should, however, be the default behavior in
40 // LTO.
42  "enable-linkonceodr-ir-outlining", cl::Hidden,
43  cl::desc("Enable the IR outliner on linkonceodr functions"),
44  cl::init(false));
45 
46 // This is a debug option to test small pieces of code to ensure that outlining
47 // works correctly.
49  "ir-outlining-no-cost", cl::init(false), cl::ReallyHidden,
50  cl::desc("Debug option to outline greedily, without restriction that "
51  "calculated benefit outweighs cost"));
52 
53 /// The OutlinableGroup holds all the overarching information for outlining
54 /// a set of regions that are structurally similar to one another, such as the
55 /// types of the overall function, the output blocks, the sets of stores needed
56 /// and a list of the different regions. This information is used in the
57 /// deduplication of extracted regions with the same structure.
59  /// The sections that could be outlined
60  std::vector<OutlinableRegion *> Regions;
61 
62  /// The argument types for the function created as the overall function to
63  /// replace the extracted function for each region.
64  std::vector<Type *> ArgumentTypes;
65  /// The FunctionType for the overall function.
66  FunctionType *OutlinedFunctionType = nullptr;
67  /// The Function for the collective overall function.
68  Function *OutlinedFunction = nullptr;
69 
70  /// Flag for whether we should not consider this group of OutlinableRegions
71  /// for extraction.
72  bool IgnoreGroup = false;
73 
74  /// The return block for the overall function.
75  BasicBlock *EndBB = nullptr;
76 
77  /// A set containing the different GVN store sets needed. Each array contains
78  /// a sorted list of the different values that need to be stored into output
79  /// registers.
81 
82  /// Flag for whether the \ref ArgumentTypes have been defined after the
83  /// extraction of the first region.
84  bool InputTypesSet = false;
85 
86  /// The number of input values in \ref ArgumentTypes. Anything after this
87  /// index in ArgumentTypes is an output argument.
88  unsigned NumAggregateInputs = 0;
89 
90  /// The number of instructions that will be outlined by extracting \ref
91  /// Regions.
92  InstructionCost Benefit = 0;
93  /// The number of added instructions needed for the outlining of the \ref
94  /// Regions.
95  InstructionCost Cost = 0;
96 
97  /// The argument that needs to be marked with the swifterr attribute. If not
98  /// needed, there is no value.
100 
101  /// For the \ref Regions, we look at every Value. If it is a constant,
102  /// we check whether it is the same in Region.
103  ///
104  /// \param [in,out] NotSame contains the global value numbers where the
105  /// constant is not always the same, and must be passed in as an argument.
106  void findSameConstants(DenseSet<unsigned> &NotSame);
107 
108  /// For the regions, look at each set of GVN stores needed and account for
109  /// each combination. Add an argument to the argument types if there is
110  /// more than one combination.
111  ///
112  /// \param [in] M - The module we are outlining from.
113  void collectGVNStoreSets(Module &M);
114 };
115 
116 /// Move the contents of \p SourceBB to before the last instruction of \p
117 /// TargetBB.
118 /// \param SourceBB - the BasicBlock to pull Instructions from.
119 /// \param TargetBB - the BasicBlock to put Instruction into.
120 static void moveBBContents(BasicBlock &SourceBB, BasicBlock &TargetBB) {
121  BasicBlock::iterator BBCurr, BBEnd, BBNext;
122  for (BBCurr = SourceBB.begin(), BBEnd = SourceBB.end(); BBCurr != BBEnd;
123  BBCurr = BBNext) {
124  BBNext = std::next(BBCurr);
125  BBCurr->moveBefore(TargetBB, TargetBB.end());
126  }
127 }
128 
130  assert(!CandidateSplit && "Candidate already split!");
131 
132  Instruction *StartInst = (*Candidate->begin()).Inst;
133  Instruction *EndInst = (*Candidate->end()).Inst;
134  assert(StartInst && EndInst && "Expected a start and end instruction?");
135  StartBB = StartInst->getParent();
136  PrevBB = StartBB;
137 
138  // The basic block gets split like so:
139  // block: block:
140  // inst1 inst1
141  // inst2 inst2
142  // region1 br block_to_outline
143  // region2 block_to_outline:
144  // region3 -> region1
145  // region4 region2
146  // inst3 region3
147  // inst4 region4
148  // br block_after_outline
149  // block_after_outline:
150  // inst3
151  // inst4
152 
153  std::string OriginalName = PrevBB->getName().str();
154 
155  StartBB = PrevBB->splitBasicBlock(StartInst, OriginalName + "_to_outline");
156 
157  // This is the case for the inner block since we do not have to include
158  // multiple blocks.
159  EndBB = StartBB;
160  FollowBB = EndBB->splitBasicBlock(EndInst, OriginalName + "_after_outline");
161 
162  CandidateSplit = true;
163 }
164 
166  assert(CandidateSplit && "Candidate is not split!");
167 
168  // The basic block gets reattached like so:
169  // block: block:
170  // inst1 inst1
171  // inst2 inst2
172  // br block_to_outline region1
173  // block_to_outline: -> region2
174  // region1 region3
175  // region2 region4
176  // region3 inst3
177  // region4 inst4
178  // br block_after_outline
179  // block_after_outline:
180  // inst3
181  // inst4
182  assert(StartBB != nullptr && "StartBB for Candidate is not defined!");
183  assert(FollowBB != nullptr && "StartBB for Candidate is not defined!");
184 
185  // StartBB should only have one predecessor since we put an unconditional
186  // branch at the end of PrevBB when we split the BasicBlock.
187  PrevBB = StartBB->getSinglePredecessor();
188  assert(PrevBB != nullptr &&
189  "No Predecessor for the region start basic block!");
190 
191  assert(PrevBB->getTerminator() && "Terminator removed from PrevBB!");
192  assert(EndBB->getTerminator() && "Terminator removed from EndBB!");
193  PrevBB->getTerminator()->eraseFromParent();
194  EndBB->getTerminator()->eraseFromParent();
195 
196  moveBBContents(*StartBB, *PrevBB);
197 
198  BasicBlock *PlacementBB = PrevBB;
199  if (StartBB != EndBB)
200  PlacementBB = EndBB;
201  moveBBContents(*FollowBB, *PlacementBB);
202 
203  PrevBB->replaceSuccessorsPhiUsesWith(StartBB, PrevBB);
204  PrevBB->replaceSuccessorsPhiUsesWith(FollowBB, PlacementBB);
205  StartBB->eraseFromParent();
206  FollowBB->eraseFromParent();
207 
208  // Make sure to save changes back to the StartBB.
209  StartBB = PrevBB;
210  EndBB = nullptr;
211  PrevBB = nullptr;
212  FollowBB = nullptr;
213 
214  CandidateSplit = false;
215 }
216 
217 /// Find whether \p V matches the Constants previously found for the \p GVN.
218 ///
219 /// \param V - The value to check for consistency.
220 /// \param GVN - The global value number assigned to \p V.
221 /// \param GVNToConstant - The mapping of global value number to Constants.
222 /// \returns true if the Value matches the Constant mapped to by V and false if
223 /// it \p V is a Constant but does not match.
224 /// \returns None if \p V is not a Constant.
225 static Optional<bool>
226 constantMatches(Value *V, unsigned GVN,
227  DenseMap<unsigned, Constant *> &GVNToConstant) {
228  // See if we have a constants
229  Constant *CST = dyn_cast<Constant>(V);
230  if (!CST)
231  return None;
232 
233  // Holds a mapping from a global value number to a Constant.
235  bool Inserted;
236 
237 
238  // If we have a constant, try to make a new entry in the GVNToConstant.
239  std::tie(GVNToConstantIt, Inserted) =
240  GVNToConstant.insert(std::make_pair(GVN, CST));
241  // If it was found and is not equal, it is not the same. We do not
242  // handle this case yet, and exit early.
243  if (Inserted || (GVNToConstantIt->second == CST))
244  return true;
245 
246  return false;
247 }
248 
250  InstructionCost Benefit = 0;
251 
252  // Estimate the benefit of outlining a specific sections of the program. We
253  // delegate mostly this task to the TargetTransformInfo so that if the target
254  // has specific changes, we can have a more accurate estimate.
255 
256  // However, getInstructionCost delegates the code size calculation for
257  // arithmetic instructions to getArithmeticInstrCost in
258  // include/Analysis/TargetTransformImpl.h, where it always estimates that the
259  // code size for a division and remainder instruction to be equal to 4, and
260  // everything else to 1. This is not an accurate representation of the
261  // division instruction for targets that have a native division instruction.
262  // To be overly conservative, we only add 1 to the number of instructions for
263  // each division instruction.
264  for (Instruction &I : *StartBB) {
265  switch (I.getOpcode()) {
266  case Instruction::FDiv:
267  case Instruction::FRem:
268  case Instruction::SDiv:
269  case Instruction::SRem:
270  case Instruction::UDiv:
271  case Instruction::URem:
272  Benefit += 1;
273  break;
274  default:
276  break;
277  }
278  }
279 
280  return Benefit;
281 }
282 
283 /// Find whether \p Region matches the global value numbering to Constant
284 /// mapping found so far.
285 ///
286 /// \param Region - The OutlinableRegion we are checking for constants
287 /// \param GVNToConstant - The mapping of global value number to Constants.
288 /// \param NotSame - The set of global value numbers that do not have the same
289 /// constant in each region.
290 /// \returns true if all Constants are the same in every use of a Constant in \p
291 /// Region and false if not
292 static bool
294  DenseMap<unsigned, Constant *> &GVNToConstant,
295  DenseSet<unsigned> &NotSame) {
296  bool ConstantsTheSame = true;
297 
298  IRSimilarityCandidate &C = *Region.Candidate;
299  for (IRInstructionData &ID : C) {
300 
301  // Iterate over the operands in an instruction. If the global value number,
302  // assigned by the IRSimilarityCandidate, has been seen before, we check if
303  // the the number has been found to be not the same value in each instance.
304  for (Value *V : ID.OperVals) {
305  Optional<unsigned> GVNOpt = C.getGVN(V);
306  assert(GVNOpt.hasValue() && "Expected a GVN for operand?");
307  unsigned GVN = GVNOpt.getValue();
308 
309  // Check if this global value has been found to not be the same already.
310  if (NotSame.contains(GVN)) {
311  if (isa<Constant>(V))
312  ConstantsTheSame = false;
313  continue;
314  }
315 
316  // If it has been the same so far, we check the value for if the
317  // associated Constant value match the previous instances of the same
318  // global value number. If the global value does not map to a Constant,
319  // it is considered to not be the same value.
320  Optional<bool> ConstantMatches = constantMatches(V, GVN, GVNToConstant);
321  if (ConstantMatches.hasValue()) {
322  if (ConstantMatches.getValue())
323  continue;
324  else
325  ConstantsTheSame = false;
326  }
327 
328  // While this value is a register, it might not have been previously,
329  // make sure we don't already have a constant mapped to this global value
330  // number.
331  if (GVNToConstant.find(GVN) != GVNToConstant.end())
332  ConstantsTheSame = false;
333 
334  NotSame.insert(GVN);
335  }
336  }
337 
338  return ConstantsTheSame;
339 }
340 
342  DenseMap<unsigned, Constant *> GVNToConstant;
343 
344  for (OutlinableRegion *Region : Regions)
345  collectRegionsConstants(*Region, GVNToConstant, NotSame);
346 }
347 
349  for (OutlinableRegion *OS : Regions)
350  OutputGVNCombinations.insert(OS->GVNStores);
351 
352  // We are adding an extracted argument to decide between which output path
353  // to use in the basic block. It is used in a switch statement and only
354  // needs to be an integer.
355  if (OutputGVNCombinations.size() > 1)
356  ArgumentTypes.push_back(Type::getInt32Ty(M.getContext()));
357 }
358 
359 /// Get the subprogram if it exists for one of the outlined regions.
360 ///
361 /// \param [in] Group - The set of regions to find a subprogram for.
362 /// \returns the subprogram if it exists, or nullptr.
364  for (OutlinableRegion *OS : Group.Regions)
365  if (Function *F = OS->Call->getFunction())
366  if (DISubprogram *SP = F->getSubprogram())
367  return SP;
368 
369  return nullptr;
370 }
371 
372 Function *IROutliner::createFunction(Module &M, OutlinableGroup &Group,
373  unsigned FunctionNameSuffix) {
374  assert(!Group.OutlinedFunction && "Function is already defined!");
375 
377  Type::getVoidTy(M.getContext()), Group.ArgumentTypes, false);
378 
379  // These functions will only be called from within the same module, so
380  // we can set an internal linkage.
383  "outlined_ir_func_" + std::to_string(FunctionNameSuffix), M);
384 
385  // Transfer the swifterr attribute to the correct function parameter.
386  if (Group.SwiftErrorArgument.hasValue())
388  Attribute::SwiftError);
389 
390  Group.OutlinedFunction->addFnAttr(Attribute::OptimizeForSize);
391  Group.OutlinedFunction->addFnAttr(Attribute::MinSize);
392 
393  // If there's a DISubprogram associated with this outlined function, then
394  // emit debug info for the outlined function.
395  if (DISubprogram *SP = getSubprogramOrNull(Group)) {
396  Function *F = Group.OutlinedFunction;
397  // We have a DISubprogram. Get its DICompileUnit.
398  DICompileUnit *CU = SP->getUnit();
399  DIBuilder DB(M, true, CU);
400  DIFile *Unit = SP->getFile();
401  Mangler Mg;
402  // Get the mangled name of the function for the linkage name.
403  std::string Dummy;
404  llvm::raw_string_ostream MangledNameStream(Dummy);
405  Mg.getNameWithPrefix(MangledNameStream, F, false);
406 
407  DISubprogram *OutlinedSP = DB.createFunction(
408  Unit /* Context */, F->getName(), MangledNameStream.str(),
409  Unit /* File */,
410  0 /* Line 0 is reserved for compiler-generated code. */,
411  DB.createSubroutineType(DB.getOrCreateTypeArray(None)), /* void type */
412  0, /* Line 0 is reserved for compiler-generated code. */
413  DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
414  /* Outlined code is optimized code by definition. */
415  DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
416 
417  // Don't add any new variables to the subprogram.
418  DB.finalizeSubprogram(OutlinedSP);
419 
420  // Attach subprogram to the function.
421  F->setSubprogram(OutlinedSP);
422  // We're done with the DIBuilder.
423  DB.finalize();
424  }
425 
426  return Group.OutlinedFunction;
427 }
428 
429 /// Move each BasicBlock in \p Old to \p New.
430 ///
431 /// \param [in] Old - The function to move the basic blocks from.
432 /// \param [in] New - The function to move the basic blocks to.
433 /// \returns the first return block for the function in New.
435  Function::iterator CurrBB, NextBB, FinalBB;
436  BasicBlock *NewEnd = nullptr;
437  std::vector<Instruction *> DebugInsts;
438  for (CurrBB = Old.begin(), FinalBB = Old.end(); CurrBB != FinalBB;
439  CurrBB = NextBB) {
440  NextBB = std::next(CurrBB);
441  CurrBB->removeFromParent();
442  CurrBB->insertInto(&New);
443  Instruction *I = CurrBB->getTerminator();
444  if (isa<ReturnInst>(I))
445  NewEnd = &(*CurrBB);
446 
447  for (Instruction &Val : *CurrBB) {
448  // We must handle the scoping of called functions differently than
449  // other outlined instructions.
450  if (!isa<CallInst>(&Val)) {
451  // Remove the debug information for outlined functions.
452  Val.setDebugLoc(DebugLoc());
453  continue;
454  }
455 
456  // From this point we are only handling call instructions.
457  CallInst *CI = cast<CallInst>(&Val);
458 
459  // We add any debug statements here, to be removed after. Since the
460  // instructions originate from many different locations in the program,
461  // it will cause incorrect reporting from a debugger if we keep the
462  // same debug instructions.
463  if (isa<DbgInfoIntrinsic>(CI)) {
464  DebugInsts.push_back(&Val);
465  continue;
466  }
467 
468  // Edit the scope of called functions inside of outlined functions.
469  if (DISubprogram *SP = New.getSubprogram()) {
470  DILocation *DI = DILocation::get(New.getContext(), 0, 0, SP);
471  Val.setDebugLoc(DI);
472  }
473  }
474 
475  for (Instruction *I : DebugInsts)
476  I->eraseFromParent();
477  }
478 
479  assert(NewEnd && "No return instruction for new function?");
480  return NewEnd;
481 }
482 
483 /// Find the the constants that will need to be lifted into arguments
484 /// as they are not the same in each instance of the region.
485 ///
486 /// \param [in] C - The IRSimilarityCandidate containing the region we are
487 /// analyzing.
488 /// \param [in] NotSame - The set of global value numbers that do not have a
489 /// single Constant across all OutlinableRegions similar to \p C.
490 /// \param [out] Inputs - The list containing the global value numbers of the
491 /// arguments needed for the region of code.
493  std::vector<unsigned> &Inputs) {
494  DenseSet<unsigned> Seen;
495  // Iterate over the instructions, and find what constants will need to be
496  // extracted into arguments.
497  for (IRInstructionDataList::iterator IDIt = C.begin(), EndIDIt = C.end();
498  IDIt != EndIDIt; IDIt++) {
499  for (Value *V : (*IDIt).OperVals) {
500  // Since these are stored before any outlining, they will be in the
501  // global value numbering.
502  unsigned GVN = C.getGVN(V).getValue();
503  if (isa<Constant>(V))
504  if (NotSame.contains(GVN) && !Seen.contains(GVN)) {
505  Inputs.push_back(GVN);
506  Seen.insert(GVN);
507  }
508  }
509  }
510 }
511 
512 /// Find the GVN for the inputs that have been found by the CodeExtractor.
513 ///
514 /// \param [in] C - The IRSimilarityCandidate containing the region we are
515 /// analyzing.
516 /// \param [in] CurrentInputs - The set of inputs found by the
517 /// CodeExtractor.
518 /// \param [in] OutputMappings - The mapping of values that have been replaced
519 /// by a new output value.
520 /// \param [out] EndInputNumbers - The global value numbers for the extracted
521 /// arguments.
523  SetVector<Value *> &CurrentInputs,
524  const DenseMap<Value *, Value *> &OutputMappings,
525  std::vector<unsigned> &EndInputNumbers) {
526  // Get the Global Value Number for each input. We check if the Value has been
527  // replaced by a different value at output, and use the original value before
528  // replacement.
529  for (Value *Input : CurrentInputs) {
530  assert(Input && "Have a nullptr as an input");
531  if (OutputMappings.find(Input) != OutputMappings.end())
532  Input = OutputMappings.find(Input)->second;
533  assert(C.getGVN(Input).hasValue() &&
534  "Could not find a numbering for the given input");
535  EndInputNumbers.push_back(C.getGVN(Input).getValue());
536  }
537 }
538 
539 /// Find the original value for the \p ArgInput values if any one of them was
540 /// replaced during a previous extraction.
541 ///
542 /// \param [in] ArgInputs - The inputs to be extracted by the code extractor.
543 /// \param [in] OutputMappings - The mapping of values that have been replaced
544 /// by a new output value.
545 /// \param [out] RemappedArgInputs - The remapped values according to
546 /// \p OutputMappings that will be extracted.
547 static void
549  const DenseMap<Value *, Value *> &OutputMappings,
550  SetVector<Value *> &RemappedArgInputs) {
551  // Get the global value number for each input that will be extracted as an
552  // argument by the code extractor, remapping if needed for reloaded values.
553  for (Value *Input : ArgInputs) {
554  if (OutputMappings.find(Input) != OutputMappings.end())
555  Input = OutputMappings.find(Input)->second;
556  RemappedArgInputs.insert(Input);
557  }
558 }
559 
560 /// Find the input GVNs and the output values for a region of Instructions.
561 /// Using the code extractor, we collect the inputs to the extracted function.
562 ///
563 /// The \p Region can be identified as needing to be ignored in this function.
564 /// It should be checked whether it should be ignored after a call to this
565 /// function.
566 ///
567 /// \param [in,out] Region - The region of code to be analyzed.
568 /// \param [out] InputGVNs - The global value numbers for the extracted
569 /// arguments.
570 /// \param [in] NotSame - The global value numbers in the region that do not
571 /// have the same constant value in the regions structurally similar to
572 /// \p Region.
573 /// \param [in] OutputMappings - The mapping of values that have been replaced
574 /// by a new output value after extraction.
575 /// \param [out] ArgInputs - The values of the inputs to the extracted function.
576 /// \param [out] Outputs - The set of values extracted by the CodeExtractor
577 /// as outputs.
579  OutlinableRegion &Region, std::vector<unsigned> &InputGVNs,
580  DenseSet<unsigned> &NotSame, DenseMap<Value *, Value *> &OutputMappings,
581  SetVector<Value *> &ArgInputs, SetVector<Value *> &Outputs) {
582  IRSimilarityCandidate &C = *Region.Candidate;
583 
584  // OverallInputs are the inputs to the region found by the CodeExtractor,
585  // SinkCands and HoistCands are used by the CodeExtractor to find sunken
586  // allocas of values whose lifetimes are contained completely within the
587  // outlined region. PremappedInputs are the arguments found by the
588  // CodeExtractor, removing conditions such as sunken allocas, but that
589  // may need to be remapped due to the extracted output values replacing
590  // the original values. We use DummyOutputs for this first run of finding
591  // inputs and outputs since the outputs could change during findAllocas,
592  // the correct set of extracted outputs will be in the final Outputs ValueSet.
593  SetVector<Value *> OverallInputs, PremappedInputs, SinkCands, HoistCands,
594  DummyOutputs;
595 
596  // Use the code extractor to get the inputs and outputs, without sunken
597  // allocas or removing llvm.assumes.
598  CodeExtractor *CE = Region.CE;
599  CE->findInputsOutputs(OverallInputs, DummyOutputs, SinkCands);
600  assert(Region.StartBB && "Region must have a start BasicBlock!");
601  Function *OrigF = Region.StartBB->getParent();
602  CodeExtractorAnalysisCache CEAC(*OrigF);
603  BasicBlock *Dummy = nullptr;
604 
605  // The region may be ineligible due to VarArgs in the parent function. In this
606  // case we ignore the region.
607  if (!CE->isEligible()) {
608  Region.IgnoreRegion = true;
609  return;
610  }
611 
612  // Find if any values are going to be sunk into the function when extracted
613  CE->findAllocas(CEAC, SinkCands, HoistCands, Dummy);
614  CE->findInputsOutputs(PremappedInputs, Outputs, SinkCands);
615 
616  // TODO: Support regions with sunken allocas: values whose lifetimes are
617  // contained completely within the outlined region. These are not guaranteed
618  // to be the same in every region, so we must elevate them all to arguments
619  // when they appear. If these values are not equal, it means there is some
620  // Input in OverallInputs that was removed for ArgInputs.
621  if (OverallInputs.size() != PremappedInputs.size()) {
622  Region.IgnoreRegion = true;
623  return;
624  }
625 
626  findConstants(C, NotSame, InputGVNs);
627 
628  mapInputsToGVNs(C, OverallInputs, OutputMappings, InputGVNs);
629 
630  remapExtractedInputs(PremappedInputs.getArrayRef(), OutputMappings,
631  ArgInputs);
632 
633  // Sort the GVNs, since we now have constants included in the \ref InputGVNs
634  // we need to make sure they are in a deterministic order.
635  stable_sort(InputGVNs);
636 }
637 
638 /// Look over the inputs and map each input argument to an argument in the
639 /// overall function for the OutlinableRegions. This creates a way to replace
640 /// the arguments of the extracted function with the arguments of the new
641 /// overall function.
642 ///
643 /// \param [in,out] Region - The region of code to be analyzed.
644 /// \param [in] InputGVNs - The global value numbering of the input values
645 /// collected.
646 /// \param [in] ArgInputs - The values of the arguments to the extracted
647 /// function.
648 static void
650  std::vector<unsigned> &InputGVNs,
651  SetVector<Value *> &ArgInputs) {
652 
653  IRSimilarityCandidate &C = *Region.Candidate;
654  OutlinableGroup &Group = *Region.Parent;
655 
656  // This counts the argument number in the overall function.
657  unsigned TypeIndex = 0;
658 
659  // This counts the argument number in the extracted function.
660  unsigned OriginalIndex = 0;
661 
662  // Find the mapping of the extracted arguments to the arguments for the
663  // overall function. Since there may be extra arguments in the overall
664  // function to account for the extracted constants, we have two different
665  // counters as we find extracted arguments, and as we come across overall
666  // arguments.
667  for (unsigned InputVal : InputGVNs) {
668  Optional<Value *> InputOpt = C.fromGVN(InputVal);
669  assert(InputOpt.hasValue() && "Global value number not found?");
670  Value *Input = InputOpt.getValue();
671 
672  if (!Group.InputTypesSet) {
673  Group.ArgumentTypes.push_back(Input->getType());
674  // If the input value has a swifterr attribute, make sure to mark the
675  // argument in the overall function.
676  if (Input->isSwiftError()) {
677  assert(
678  !Group.SwiftErrorArgument.hasValue() &&
679  "Argument already marked with swifterr for this OutlinableGroup!");
680  Group.SwiftErrorArgument = TypeIndex;
681  }
682  }
683 
684  // Check if we have a constant. If we do add it to the overall argument
685  // number to Constant map for the region, and continue to the next input.
686  if (Constant *CST = dyn_cast<Constant>(Input)) {
687  Region.AggArgToConstant.insert(std::make_pair(TypeIndex, CST));
688  TypeIndex++;
689  continue;
690  }
691 
692  // It is not a constant, we create the mapping from extracted argument list
693  // to the overall argument list.
694  assert(ArgInputs.count(Input) && "Input cannot be found!");
695 
696  Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, TypeIndex));
697  Region.AggArgToExtracted.insert(std::make_pair(TypeIndex, OriginalIndex));
698  OriginalIndex++;
699  TypeIndex++;
700  }
701 
702  // If the function type definitions for the OutlinableGroup holding the region
703  // have not been set, set the length of the inputs here. We should have the
704  // same inputs for all of the different regions contained in the
705  // OutlinableGroup since they are all structurally similar to one another.
706  if (!Group.InputTypesSet) {
707  Group.NumAggregateInputs = TypeIndex;
708  Group.InputTypesSet = true;
709  }
710 
711  Region.NumExtractedInputs = OriginalIndex;
712 }
713 
714 /// Create a mapping of the output arguments for the \p Region to the output
715 /// arguments of the overall outlined function.
716 ///
717 /// \param [in,out] Region - The region of code to be analyzed.
718 /// \param [in] Outputs - The values found by the code extractor.
719 static void
721  ArrayRef<Value *> Outputs) {
722  OutlinableGroup &Group = *Region.Parent;
723  IRSimilarityCandidate &C = *Region.Candidate;
724 
725  // This counts the argument number in the extracted function.
726  unsigned OriginalIndex = Region.NumExtractedInputs;
727 
728  // This counts the argument number in the overall function.
729  unsigned TypeIndex = Group.NumAggregateInputs;
730  bool TypeFound;
731  DenseSet<unsigned> AggArgsUsed;
732 
733  // Iterate over the output types and identify if there is an aggregate pointer
734  // type whose base type matches the current output type. If there is, we mark
735  // that we will use this output register for this value. If not we add another
736  // type to the overall argument type list. We also store the GVNs used for
737  // stores to identify which values will need to be moved into an special
738  // block that holds the stores to the output registers.
739  for (Value *Output : Outputs) {
740  TypeFound = false;
741  // We can do this since it is a result value, and will have a number
742  // that is necessarily the same. BUT if in the future, the instructions
743  // do not have to be in same order, but are functionally the same, we will
744  // have to use a different scheme, as one-to-one correspondence is not
745  // guaranteed.
746  unsigned GlobalValue = C.getGVN(Output).getValue();
747  unsigned ArgumentSize = Group.ArgumentTypes.size();
748 
749  for (unsigned Jdx = TypeIndex; Jdx < ArgumentSize; Jdx++) {
750  if (Group.ArgumentTypes[Jdx] != PointerType::getUnqual(Output->getType()))
751  continue;
752 
753  if (AggArgsUsed.contains(Jdx))
754  continue;
755 
756  TypeFound = true;
757  AggArgsUsed.insert(Jdx);
758  Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, Jdx));
759  Region.AggArgToExtracted.insert(std::make_pair(Jdx, OriginalIndex));
760  Region.GVNStores.push_back(GlobalValue);
761  break;
762  }
763 
764  // We were unable to find an unused type in the output type set that matches
765  // the output, so we add a pointer type to the argument types of the overall
766  // function to handle this output and create a mapping to it.
767  if (!TypeFound) {
768  Group.ArgumentTypes.push_back(PointerType::getUnqual(Output->getType()));
769  AggArgsUsed.insert(Group.ArgumentTypes.size() - 1);
770  Region.ExtractedArgToAgg.insert(
771  std::make_pair(OriginalIndex, Group.ArgumentTypes.size() - 1));
772  Region.AggArgToExtracted.insert(
773  std::make_pair(Group.ArgumentTypes.size() - 1, OriginalIndex));
774  Region.GVNStores.push_back(GlobalValue);
775  }
776 
777  stable_sort(Region.GVNStores);
778  OriginalIndex++;
779  TypeIndex++;
780  }
781 }
782 
783 void IROutliner::findAddInputsOutputs(Module &M, OutlinableRegion &Region,
784  DenseSet<unsigned> &NotSame) {
785  std::vector<unsigned> Inputs;
786  SetVector<Value *> ArgInputs, Outputs;
787 
788  getCodeExtractorArguments(Region, Inputs, NotSame, OutputMappings, ArgInputs,
789  Outputs);
790 
791  if (Region.IgnoreRegion)
792  return;
793 
794  // Map the inputs found by the CodeExtractor to the arguments found for
795  // the overall function.
797 
798  // Map the outputs found by the CodeExtractor to the arguments found for
799  // the overall function.
801 }
802 
803 /// Replace the extracted function in the Region with a call to the overall
804 /// function constructed from the deduplicated similar regions, replacing and
805 /// remapping the values passed to the extracted function as arguments to the
806 /// new arguments of the overall function.
807 ///
808 /// \param [in] M - The module to outline from.
809 /// \param [in] Region - The regions of extracted code to be replaced with a new
810 /// function.
811 /// \returns a call instruction with the replaced function.
813  std::vector<Value *> NewCallArgs;
815 
816  OutlinableGroup &Group = *Region.Parent;
817  CallInst *Call = Region.Call;
818  assert(Call && "Call to replace is nullptr?");
819  Function *AggFunc = Group.OutlinedFunction;
820  assert(AggFunc && "Function to replace with is nullptr?");
821 
822  // If the arguments are the same size, there are not values that need to be
823  // made argument, or different output registers to handle. We can simply
824  // replace the called function in this case.
825  if (AggFunc->arg_size() == Call->arg_size()) {
826  LLVM_DEBUG(dbgs() << "Replace call to " << *Call << " with call to "
827  << *AggFunc << " with same number of arguments\n");
828  Call->setCalledFunction(AggFunc);
829  return Call;
830  }
831 
832  // We have a different number of arguments than the new function, so
833  // we need to use our previously mappings off extracted argument to overall
834  // function argument, and constants to overall function argument to create the
835  // new argument list.
836  for (unsigned AggArgIdx = 0; AggArgIdx < AggFunc->arg_size(); AggArgIdx++) {
837 
838  if (AggArgIdx == AggFunc->arg_size() - 1 &&
839  Group.OutputGVNCombinations.size() > 1) {
840  // If we are on the last argument, and we need to differentiate between
841  // output blocks, add an integer to the argument list to determine
842  // what block to take
843  LLVM_DEBUG(dbgs() << "Set switch block argument to "
844  << Region.OutputBlockNum << "\n");
845  NewCallArgs.push_back(ConstantInt::get(Type::getInt32Ty(M.getContext()),
846  Region.OutputBlockNum));
847  continue;
848  }
849 
850  ArgPair = Region.AggArgToExtracted.find(AggArgIdx);
851  if (ArgPair != Region.AggArgToExtracted.end()) {
852  Value *ArgumentValue = Call->getArgOperand(ArgPair->second);
853  // If we found the mapping from the extracted function to the overall
854  // function, we simply add it to the argument list. We use the same
855  // value, it just needs to honor the new order of arguments.
856  LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to value "
857  << *ArgumentValue << "\n");
858  NewCallArgs.push_back(ArgumentValue);
859  continue;
860  }
861 
862  // If it is a constant, we simply add it to the argument list as a value.
863  if (Region.AggArgToConstant.find(AggArgIdx) !=
864  Region.AggArgToConstant.end()) {
865  Constant *CST = Region.AggArgToConstant.find(AggArgIdx)->second;
866  LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to value "
867  << *CST << "\n");
868  NewCallArgs.push_back(CST);
869  continue;
870  }
871 
872  // Add a nullptr value if the argument is not found in the extracted
873  // function. If we cannot find a value, it means it is not in use
874  // for the region, so we should not pass anything to it.
875  LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to nullptr\n");
876  NewCallArgs.push_back(ConstantPointerNull::get(
877  static_cast<PointerType *>(AggFunc->getArg(AggArgIdx)->getType())));
878  }
879 
880  LLVM_DEBUG(dbgs() << "Replace call to " << *Call << " with call to "
881  << *AggFunc << " with new set of arguments\n");
882  // Create the new call instruction and erase the old one.
883  Call = CallInst::Create(AggFunc->getFunctionType(), AggFunc, NewCallArgs, "",
884  Call);
885 
886  // It is possible that the call to the outlined function is either the first
887  // instruction is in the new block, the last instruction, or both. If either
888  // of these is the case, we need to make sure that we replace the instruction
889  // in the IRInstructionData struct with the new call.
890  CallInst *OldCall = Region.Call;
891  if (Region.NewFront->Inst == OldCall)
892  Region.NewFront->Inst = Call;
893  if (Region.NewBack->Inst == OldCall)
894  Region.NewBack->Inst = Call;
895 
896  // Transfer any debug information.
897  Call->setDebugLoc(Region.Call->getDebugLoc());
898 
899  // Remove the old instruction.
900  OldCall->eraseFromParent();
901  Region.Call = Call;
902 
903  // Make sure that the argument in the new function has the SwiftError
904  // argument.
905  if (Group.SwiftErrorArgument.hasValue())
906  Call->addParamAttr(Group.SwiftErrorArgument.getValue(),
907  Attribute::SwiftError);
908 
909  return Call;
910 }
911 
912 // Within an extracted function, replace the argument uses of the extracted
913 // region with the arguments of the function for an OutlinableGroup.
914 //
915 /// \param [in] Region - The region of extracted code to be changed.
916 /// \param [in,out] OutputBB - The BasicBlock for the output stores for this
917 /// region.
919  BasicBlock *OutputBB) {
920  OutlinableGroup &Group = *Region.Parent;
921  assert(Region.ExtractedFunction && "Region has no extracted function?");
922 
923  for (unsigned ArgIdx = 0; ArgIdx < Region.ExtractedFunction->arg_size();
924  ArgIdx++) {
925  assert(Region.ExtractedArgToAgg.find(ArgIdx) !=
926  Region.ExtractedArgToAgg.end() &&
927  "No mapping from extracted to outlined?");
928  unsigned AggArgIdx = Region.ExtractedArgToAgg.find(ArgIdx)->second;
929  Argument *AggArg = Group.OutlinedFunction->getArg(AggArgIdx);
930  Argument *Arg = Region.ExtractedFunction->getArg(ArgIdx);
931  // The argument is an input, so we can simply replace it with the overall
932  // argument value
933  if (ArgIdx < Region.NumExtractedInputs) {
934  LLVM_DEBUG(dbgs() << "Replacing uses of input " << *Arg << " in function "
935  << *Region.ExtractedFunction << " with " << *AggArg
936  << " in function " << *Group.OutlinedFunction << "\n");
937  Arg->replaceAllUsesWith(AggArg);
938  continue;
939  }
940 
941  // If we are replacing an output, we place the store value in its own
942  // block inside the overall function before replacing the use of the output
943  // in the function.
944  assert(Arg->hasOneUse() && "Output argument can only have one use");
945  User *InstAsUser = Arg->user_back();
946  assert(InstAsUser && "User is nullptr!");
947 
948  Instruction *I = cast<Instruction>(InstAsUser);
949  I->setDebugLoc(DebugLoc());
950  LLVM_DEBUG(dbgs() << "Move store for instruction " << *I << " to "
951  << *OutputBB << "\n");
952 
953  I->moveBefore(*OutputBB, OutputBB->end());
954 
955  LLVM_DEBUG(dbgs() << "Replacing uses of output " << *Arg << " in function "
956  << *Region.ExtractedFunction << " with " << *AggArg
957  << " in function " << *Group.OutlinedFunction << "\n");
958  Arg->replaceAllUsesWith(AggArg);
959  }
960 }
961 
962 /// Within an extracted function, replace the constants that need to be lifted
963 /// into arguments with the actual argument.
964 ///
965 /// \param Region [in] - The region of extracted code to be changed.
967  OutlinableGroup &Group = *Region.Parent;
968  // Iterate over the constants that need to be elevated into arguments
969  for (std::pair<unsigned, Constant *> &Const : Region.AggArgToConstant) {
970  unsigned AggArgIdx = Const.first;
971  Function *OutlinedFunction = Group.OutlinedFunction;
972  assert(OutlinedFunction && "Overall Function is not defined?");
973  Constant *CST = Const.second;
974  Argument *Arg = Group.OutlinedFunction->getArg(AggArgIdx);
975  // Identify the argument it will be elevated to, and replace instances of
976  // that constant in the function.
977 
978  // TODO: If in the future constants do not have one global value number,
979  // i.e. a constant 1 could be mapped to several values, this check will
980  // have to be more strict. It cannot be using only replaceUsesWithIf.
981 
982  LLVM_DEBUG(dbgs() << "Replacing uses of constant " << *CST
983  << " in function " << *OutlinedFunction << " with "
984  << *Arg << "\n");
985  CST->replaceUsesWithIf(Arg, [OutlinedFunction](Use &U) {
986  if (Instruction *I = dyn_cast<Instruction>(U.getUser()))
987  return I->getFunction() == OutlinedFunction;
988  return false;
989  });
990  }
991 }
992 
993 /// For the given function, find all the nondebug or lifetime instructions,
994 /// and return them as a vector. Exclude any blocks in \p ExludeBlocks.
995 ///
996 /// \param [in] F - The function we collect the instructions from.
997 /// \param [in] ExcludeBlocks - BasicBlocks to ignore.
998 /// \returns the list of instructions extracted.
999 static std::vector<Instruction *>
1001  DenseSet<BasicBlock *> &ExcludeBlocks) {
1002  std::vector<Instruction *> RelevantInstructions;
1003 
1004  for (BasicBlock &BB : F) {
1005  if (ExcludeBlocks.contains(&BB))
1006  continue;
1007 
1008  for (Instruction &Inst : BB) {
1009  if (Inst.isLifetimeStartOrEnd())
1010  continue;
1011  if (isa<DbgInfoIntrinsic>(Inst))
1012  continue;
1013 
1014  RelevantInstructions.push_back(&Inst);
1015  }
1016  }
1017 
1018  return RelevantInstructions;
1019 }
1020 
1021 /// It is possible that there is a basic block that already performs the same
1022 /// stores. This returns a duplicate block, if it exists
1023 ///
1024 /// \param OutputBB [in] the block we are looking for a duplicate of.
1025 /// \param OutputStoreBBs [in] The existing output blocks.
1026 /// \returns an optional value with the number output block if there is a match.
1029  ArrayRef<BasicBlock *> OutputStoreBBs) {
1030 
1031  bool WrongInst = false;
1032  bool WrongSize = false;
1033  unsigned MatchingNum = 0;
1034  for (BasicBlock *CompBB : OutputStoreBBs) {
1035  WrongInst = false;
1036  if (CompBB->size() - 1 != OutputBB->size()) {
1037  WrongSize = true;
1038  MatchingNum++;
1039  continue;
1040  }
1041 
1042  WrongSize = false;
1043  BasicBlock::iterator NIt = OutputBB->begin();
1044  for (Instruction &I : *CompBB) {
1045  if (isa<BranchInst>(&I))
1046  continue;
1047 
1048  if (!I.isIdenticalTo(&(*NIt))) {
1049  WrongInst = true;
1050  break;
1051  }
1052 
1053  NIt++;
1054  }
1055  if (!WrongInst && !WrongSize)
1056  return MatchingNum;
1057 
1058  MatchingNum++;
1059  }
1060 
1061  return None;
1062 }
1063 
1064 /// For the outlined section, move needed the StoreInsts for the output
1065 /// registers into their own block. Then, determine if there is a duplicate
1066 /// output block already created.
1067 ///
1068 /// \param [in] OG - The OutlinableGroup of regions to be outlined.
1069 /// \param [in] Region - The OutlinableRegion that is being analyzed.
1070 /// \param [in,out] OutputBB - the block that stores for this region will be
1071 /// placed in.
1072 /// \param [in] EndBB - the final block of the extracted function.
1073 /// \param [in] OutputMappings - OutputMappings the mapping of values that have
1074 /// been replaced by a new output value.
1075 /// \param [in,out] OutputStoreBBs - The existing output blocks.
1076 static void
1078  BasicBlock *OutputBB, BasicBlock *EndBB,
1079  const DenseMap<Value *, Value *> &OutputMappings,
1080  std::vector<BasicBlock *> &OutputStoreBBs) {
1081  DenseSet<unsigned> ValuesToFind(Region.GVNStores.begin(),
1082  Region.GVNStores.end());
1083 
1084  // We iterate over the instructions in the extracted function, and find the
1085  // global value number of the instructions. If we find a value that should
1086  // be contained in a store, we replace the uses of the value with the value
1087  // from the overall function, so that the store is storing the correct
1088  // value from the overall function.
1089  DenseSet<BasicBlock *> ExcludeBBs(OutputStoreBBs.begin(),
1090  OutputStoreBBs.end());
1091  ExcludeBBs.insert(OutputBB);
1092  std::vector<Instruction *> ExtractedFunctionInsts =
1093  collectRelevantInstructions(*(Region.ExtractedFunction), ExcludeBBs);
1094  std::vector<Instruction *> OverallFunctionInsts =
1096 
1097  assert(ExtractedFunctionInsts.size() == OverallFunctionInsts.size() &&
1098  "Number of relevant instructions not equal!");
1099 
1100  unsigned NumInstructions = ExtractedFunctionInsts.size();
1101  for (unsigned Idx = 0; Idx < NumInstructions; Idx++) {
1102  Value *V = ExtractedFunctionInsts[Idx];
1103 
1104  if (OutputMappings.find(V) != OutputMappings.end())
1105  V = OutputMappings.find(V)->second;
1106  Optional<unsigned> GVN = Region.Candidate->getGVN(V);
1107 
1108  // If we have found one of the stored values for output, replace the value
1109  // with the corresponding one from the overall function.
1110  if (GVN.hasValue() && ValuesToFind.erase(GVN.getValue())) {
1111  V->replaceAllUsesWith(OverallFunctionInsts[Idx]);
1112  if (ValuesToFind.size() == 0)
1113  break;
1114  }
1115 
1116  if (ValuesToFind.size() == 0)
1117  break;
1118  }
1119 
1120  assert(ValuesToFind.size() == 0 && "Not all store values were handled!");
1121 
1122  // If the size of the block is 0, then there are no stores, and we do not
1123  // need to save this block.
1124  if (OutputBB->size() == 0) {
1125  Region.OutputBlockNum = -1;
1126  OutputBB->eraseFromParent();
1127  return;
1128  }
1129 
1130  // Determine is there is a duplicate block.
1131  Optional<unsigned> MatchingBB =
1132  findDuplicateOutputBlock(OutputBB, OutputStoreBBs);
1133 
1134  // If there is, we remove the new output block. If it does not,
1135  // we add it to our list of output blocks.
1136  if (MatchingBB.hasValue()) {
1137  LLVM_DEBUG(dbgs() << "Set output block for region in function"
1138  << Region.ExtractedFunction << " to "
1139  << MatchingBB.getValue());
1140 
1141  Region.OutputBlockNum = MatchingBB.getValue();
1142  OutputBB->eraseFromParent();
1143  return;
1144  }
1145 
1146  Region.OutputBlockNum = OutputStoreBBs.size();
1147 
1148  LLVM_DEBUG(dbgs() << "Create output block for region in"
1149  << Region.ExtractedFunction << " to "
1150  << *OutputBB);
1151  OutputStoreBBs.push_back(OutputBB);
1152  BranchInst::Create(EndBB, OutputBB);
1153 }
1154 
1155 /// Create the switch statement for outlined function to differentiate between
1156 /// all the output blocks.
1157 ///
1158 /// For the outlined section, determine if an outlined block already exists that
1159 /// matches the needed stores for the extracted section.
1160 /// \param [in] M - The module we are outlining from.
1161 /// \param [in] OG - The group of regions to be outlined.
1162 /// \param [in] EndBB - The final block of the extracted function.
1163 /// \param [in,out] OutputStoreBBs - The existing output blocks.
1165  ArrayRef<BasicBlock *> OutputStoreBBs) {
1166  // We only need the switch statement if there is more than one store
1167  // combination.
1168  if (OG.OutputGVNCombinations.size() > 1) {
1169  Function *AggFunc = OG.OutlinedFunction;
1170  // Create a final block
1171  BasicBlock *ReturnBlock =
1172  BasicBlock::Create(M.getContext(), "final_block", AggFunc);
1173  Instruction *Term = EndBB->getTerminator();
1174  Term->moveBefore(*ReturnBlock, ReturnBlock->end());
1175  // Put the switch statement in the old end basic block for the function with
1176  // a fall through to the new return block
1177  LLVM_DEBUG(dbgs() << "Create switch statement in " << *AggFunc << " for "
1178  << OutputStoreBBs.size() << "\n");
1179  SwitchInst *SwitchI =
1180  SwitchInst::Create(AggFunc->getArg(AggFunc->arg_size() - 1),
1181  ReturnBlock, OutputStoreBBs.size(), EndBB);
1182 
1183  unsigned Idx = 0;
1184  for (BasicBlock *BB : OutputStoreBBs) {
1185  SwitchI->addCase(ConstantInt::get(Type::getInt32Ty(M.getContext()), Idx),
1186  BB);
1187  Term = BB->getTerminator();
1188  Term->setSuccessor(0, ReturnBlock);
1189  Idx++;
1190  }
1191  return;
1192  }
1193 
1194  // If there needs to be stores, move them from the output block to the end
1195  // block to save on branching instructions.
1196  if (OutputStoreBBs.size() == 1) {
1197  LLVM_DEBUG(dbgs() << "Move store instructions to the end block in "
1198  << *OG.OutlinedFunction << "\n");
1199  BasicBlock *OutputBlock = OutputStoreBBs[0];
1200  Instruction *Term = OutputBlock->getTerminator();
1201  Term->eraseFromParent();
1202  Term = EndBB->getTerminator();
1203  moveBBContents(*OutputBlock, *EndBB);
1204  Term->moveBefore(*EndBB, EndBB->end());
1205  OutputBlock->eraseFromParent();
1206  }
1207 }
1208 
1209 /// Fill the new function that will serve as the replacement function for all of
1210 /// the extracted regions of a certain structure from the first region in the
1211 /// list of regions. Replace this first region's extracted function with the
1212 /// new overall function.
1213 ///
1214 /// \param [in] M - The module we are outlining from.
1215 /// \param [in] CurrentGroup - The group of regions to be outlined.
1216 /// \param [in,out] OutputStoreBBs - The output blocks for each different
1217 /// set of stores needed for the different functions.
1218 /// \param [in,out] FuncsToRemove - Extracted functions to erase from module
1219 /// once outlining is complete.
1220 static void fillOverallFunction(Module &M, OutlinableGroup &CurrentGroup,
1221  std::vector<BasicBlock *> &OutputStoreBBs,
1222  std::vector<Function *> &FuncsToRemove) {
1223  OutlinableRegion *CurrentOS = CurrentGroup.Regions[0];
1224 
1225  // Move first extracted function's instructions into new function.
1226  LLVM_DEBUG(dbgs() << "Move instructions from "
1227  << *CurrentOS->ExtractedFunction << " to instruction "
1228  << *CurrentGroup.OutlinedFunction << "\n");
1229 
1230  CurrentGroup.EndBB = moveFunctionData(*CurrentOS->ExtractedFunction,
1231  *CurrentGroup.OutlinedFunction);
1232 
1233  // Transfer the attributes from the function to the new function.
1234  for (Attribute A :
1236  CurrentGroup.OutlinedFunction->addFnAttr(A);
1237 
1238  // Create an output block for the first extracted function.
1239  BasicBlock *NewBB = BasicBlock::Create(
1240  M.getContext(), Twine("output_block_") + Twine(static_cast<unsigned>(0)),
1241  CurrentGroup.OutlinedFunction);
1242  CurrentOS->OutputBlockNum = 0;
1243 
1244  replaceArgumentUses(*CurrentOS, NewBB);
1245  replaceConstants(*CurrentOS);
1246 
1247  // If the new basic block has no new stores, we can erase it from the module.
1248  // It it does, we create a branch instruction to the last basic block from the
1249  // new one.
1250  if (NewBB->size() == 0) {
1251  CurrentOS->OutputBlockNum = -1;
1252  NewBB->eraseFromParent();
1253  } else {
1254  BranchInst::Create(CurrentGroup.EndBB, NewBB);
1255  OutputStoreBBs.push_back(NewBB);
1256  }
1257 
1258  // Replace the call to the extracted function with the outlined function.
1259  CurrentOS->Call = replaceCalledFunction(M, *CurrentOS);
1260 
1261  // We only delete the extracted functions at the end since we may need to
1262  // reference instructions contained in them for mapping purposes.
1263  FuncsToRemove.push_back(CurrentOS->ExtractedFunction);
1264 }
1265 
1266 void IROutliner::deduplicateExtractedSections(
1267  Module &M, OutlinableGroup &CurrentGroup,
1268  std::vector<Function *> &FuncsToRemove, unsigned &OutlinedFunctionNum) {
1269  createFunction(M, CurrentGroup, OutlinedFunctionNum);
1270 
1271  std::vector<BasicBlock *> OutputStoreBBs;
1272 
1273  OutlinableRegion *CurrentOS;
1274 
1275  fillOverallFunction(M, CurrentGroup, OutputStoreBBs, FuncsToRemove);
1276 
1277  for (unsigned Idx = 1; Idx < CurrentGroup.Regions.size(); Idx++) {
1278  CurrentOS = CurrentGroup.Regions[Idx];
1280  *CurrentOS->ExtractedFunction);
1281 
1282  // Create a new BasicBlock to hold the needed store instructions.
1283  BasicBlock *NewBB = BasicBlock::Create(
1284  M.getContext(), "output_block_" + std::to_string(Idx),
1285  CurrentGroup.OutlinedFunction);
1286  replaceArgumentUses(*CurrentOS, NewBB);
1287 
1288  alignOutputBlockWithAggFunc(CurrentGroup, *CurrentOS, NewBB,
1289  CurrentGroup.EndBB, OutputMappings,
1290  OutputStoreBBs);
1291 
1292  CurrentOS->Call = replaceCalledFunction(M, *CurrentOS);
1293  FuncsToRemove.push_back(CurrentOS->ExtractedFunction);
1294  }
1295 
1296  // Create a switch statement to handle the different output schemes.
1297  createSwitchStatement(M, CurrentGroup, CurrentGroup.EndBB, OutputStoreBBs);
1298 
1299  OutlinedFunctionNum++;
1300 }
1301 
1302 void IROutliner::pruneIncompatibleRegions(
1303  std::vector<IRSimilarityCandidate> &CandidateVec,
1304  OutlinableGroup &CurrentGroup) {
1305  bool PreviouslyOutlined;
1306 
1307  // Sort from beginning to end, so the IRSimilarityCandidates are in order.
1308  stable_sort(CandidateVec, [](const IRSimilarityCandidate &LHS,
1309  const IRSimilarityCandidate &RHS) {
1310  return LHS.getStartIdx() < RHS.getStartIdx();
1311  });
1312 
1313  unsigned CurrentEndIdx = 0;
1314  for (IRSimilarityCandidate &IRSC : CandidateVec) {
1315  PreviouslyOutlined = false;
1316  unsigned StartIdx = IRSC.getStartIdx();
1317  unsigned EndIdx = IRSC.getEndIdx();
1318 
1319  for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
1320  if (Outlined.contains(Idx)) {
1321  PreviouslyOutlined = true;
1322  break;
1323  }
1324 
1325  if (PreviouslyOutlined)
1326  continue;
1327 
1328  // TODO: If in the future we can outline across BasicBlocks, we will need to
1329  // check all BasicBlocks contained in the region.
1330  if (IRSC.getStartBB()->hasAddressTaken())
1331  continue;
1332 
1333  if (IRSC.front()->Inst->getFunction()->hasLinkOnceODRLinkage() &&
1334  !OutlineFromLinkODRs)
1335  continue;
1336 
1337  // Greedily prune out any regions that will overlap with already chosen
1338  // regions.
1339  if (CurrentEndIdx != 0 && StartIdx <= CurrentEndIdx)
1340  continue;
1341 
1342  bool BadInst = any_of(IRSC, [this](IRInstructionData &ID) {
1343  // We check if there is a discrepancy between the InstructionDataList
1344  // and the actual next instruction in the module. If there is, it means
1345  // that an extra instruction was added, likely by the CodeExtractor.
1346 
1347  // Since we do not have any similarity data about this particular
1348  // instruction, we cannot confidently outline it, and must discard this
1349  // candidate.
1350  if (std::next(ID.getIterator())->Inst !=
1351  ID.Inst->getNextNonDebugInstruction())
1352  return true;
1353  return !this->InstructionClassifier.visit(ID.Inst);
1354  });
1355 
1356  if (BadInst)
1357  continue;
1358 
1359  OutlinableRegion *OS = new (RegionAllocator.Allocate())
1360  OutlinableRegion(IRSC, CurrentGroup);
1361  CurrentGroup.Regions.push_back(OS);
1362 
1363  CurrentEndIdx = EndIdx;
1364  }
1365 }
1366 
1368 IROutliner::findBenefitFromAllRegions(OutlinableGroup &CurrentGroup) {
1369  InstructionCost RegionBenefit = 0;
1370  for (OutlinableRegion *Region : CurrentGroup.Regions) {
1371  TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());
1372  // We add the number of instructions in the region to the benefit as an
1373  // estimate as to how much will be removed.
1374  RegionBenefit += Region->getBenefit(TTI);
1375  LLVM_DEBUG(dbgs() << "Adding: " << RegionBenefit
1376  << " saved instructions to overfall benefit.\n");
1377  }
1378 
1379  return RegionBenefit;
1380 }
1381 
1383 IROutliner::findCostOutputReloads(OutlinableGroup &CurrentGroup) {
1384  InstructionCost OverallCost = 0;
1385  for (OutlinableRegion *Region : CurrentGroup.Regions) {
1386  TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());
1387 
1388  // Each output incurs a load after the call, so we add that to the cost.
1389  for (unsigned OutputGVN : Region->GVNStores) {
1390  Optional<Value *> OV = Region->Candidate->fromGVN(OutputGVN);
1391  assert(OV.hasValue() && "Could not find value for GVN?");
1392  Value *V = OV.getValue();
1393  InstructionCost LoadCost =
1396 
1397  LLVM_DEBUG(dbgs() << "Adding: " << LoadCost
1398  << " instructions to cost for output of type "
1399  << *V->getType() << "\n");
1400  OverallCost += LoadCost;
1401  }
1402  }
1403 
1404  return OverallCost;
1405 }
1406 
1407 /// Find the extra instructions needed to handle any output values for the
1408 /// region.
1409 ///
1410 /// \param [in] M - The Module to outline from.
1411 /// \param [in] CurrentGroup - The collection of OutlinableRegions to analyze.
1412 /// \param [in] TTI - The TargetTransformInfo used to collect information for
1413 /// new instruction costs.
1414 /// \returns the additional cost to handle the outputs.
1416  OutlinableGroup &CurrentGroup,
1418  InstructionCost OutputCost = 0;
1419 
1420  for (const ArrayRef<unsigned> &OutputUse :
1421  CurrentGroup.OutputGVNCombinations) {
1422  IRSimilarityCandidate &Candidate = *CurrentGroup.Regions[0]->Candidate;
1423  for (unsigned GVN : OutputUse) {
1424  Optional<Value *> OV = Candidate.fromGVN(GVN);
1425  assert(OV.hasValue() && "Could not find value for GVN?");
1426  Value *V = OV.getValue();
1427  InstructionCost StoreCost =
1430 
1431  // An instruction cost is added for each store set that needs to occur for
1432  // various output combinations inside the function, plus a branch to
1433  // return to the exit block.
1434  LLVM_DEBUG(dbgs() << "Adding: " << StoreCost
1435  << " instructions to cost for output of type "
1436  << *V->getType() << "\n");
1437  OutputCost += StoreCost;
1438  }
1439 
1440  InstructionCost BranchCost =
1442  LLVM_DEBUG(dbgs() << "Adding " << BranchCost << " to the current cost for"
1443  << " a branch instruction\n");
1444  OutputCost += BranchCost;
1445  }
1446 
1447  // If there is more than one output scheme, we must have a comparison and
1448  // branch for each different item in the switch statement.
1449  if (CurrentGroup.OutputGVNCombinations.size() > 1) {
1450  InstructionCost ComparisonCost = TTI.getCmpSelInstrCost(
1451  Instruction::ICmp, Type::getInt32Ty(M.getContext()),
1454  InstructionCost BranchCost =
1456 
1457  unsigned DifferentBlocks = CurrentGroup.OutputGVNCombinations.size();
1458  InstructionCost TotalCost = ComparisonCost * BranchCost * DifferentBlocks;
1459 
1460  LLVM_DEBUG(dbgs() << "Adding: " << TotalCost
1461  << " instructions for each switch case for each different"
1462  << " output path in a function\n");
1463  OutputCost += TotalCost;
1464  }
1465 
1466  return OutputCost;
1467 }
1468 
1469 void IROutliner::findCostBenefit(Module &M, OutlinableGroup &CurrentGroup) {
1470  InstructionCost RegionBenefit = findBenefitFromAllRegions(CurrentGroup);
1471  CurrentGroup.Benefit += RegionBenefit;
1472  LLVM_DEBUG(dbgs() << "Current Benefit: " << CurrentGroup.Benefit << "\n");
1473 
1474  InstructionCost OutputReloadCost = findCostOutputReloads(CurrentGroup);
1475  CurrentGroup.Cost += OutputReloadCost;
1476  LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
1477 
1478  InstructionCost AverageRegionBenefit =
1479  RegionBenefit / CurrentGroup.Regions.size();
1480  unsigned OverallArgumentNum = CurrentGroup.ArgumentTypes.size();
1481  unsigned NumRegions = CurrentGroup.Regions.size();
1483  getTTI(*CurrentGroup.Regions[0]->Candidate->getFunction());
1484 
1485  // We add one region to the cost once, to account for the instructions added
1486  // inside of the newly created function.
1487  LLVM_DEBUG(dbgs() << "Adding: " << AverageRegionBenefit
1488  << " instructions to cost for body of new function.\n");
1489  CurrentGroup.Cost += AverageRegionBenefit;
1490  LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
1491 
1492  // For each argument, we must add an instruction for loading the argument
1493  // out of the register and into a value inside of the newly outlined function.
1494  LLVM_DEBUG(dbgs() << "Adding: " << OverallArgumentNum
1495  << " instructions to cost for each argument in the new"
1496  << " function.\n");
1497  CurrentGroup.Cost +=
1498  OverallArgumentNum * TargetTransformInfo::TCC_Basic;
1499  LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
1500 
1501  // Each argument needs to either be loaded into a register or onto the stack.
1502  // Some arguments will only be loaded into the stack once the argument
1503  // registers are filled.
1504  LLVM_DEBUG(dbgs() << "Adding: " << OverallArgumentNum
1505  << " instructions to cost for each argument in the new"
1506  << " function " << NumRegions << " times for the "
1507  << "needed argument handling at the call site.\n");
1508  CurrentGroup.Cost +=
1509  2 * OverallArgumentNum * TargetTransformInfo::TCC_Basic * NumRegions;
1510  LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
1511 
1512  CurrentGroup.Cost += findCostForOutputBlocks(M, CurrentGroup, TTI);
1513  LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
1514 }
1515 
1516 void IROutliner::updateOutputMapping(OutlinableRegion &Region,
1517  ArrayRef<Value *> Outputs,
1518  LoadInst *LI) {
1519  // For and load instructions following the call
1520  Value *Operand = LI->getPointerOperand();
1521  Optional<unsigned> OutputIdx = None;
1522  // Find if the operand it is an output register.
1523  for (unsigned ArgIdx = Region.NumExtractedInputs;
1524  ArgIdx < Region.Call->arg_size(); ArgIdx++) {
1525  if (Operand == Region.Call->getArgOperand(ArgIdx)) {
1526  OutputIdx = ArgIdx - Region.NumExtractedInputs;
1527  break;
1528  }
1529  }
1530 
1531  // If we found an output register, place a mapping of the new value
1532  // to the original in the mapping.
1533  if (!OutputIdx.hasValue())
1534  return;
1535 
1536  if (OutputMappings.find(Outputs[OutputIdx.getValue()]) ==
1537  OutputMappings.end()) {
1538  LLVM_DEBUG(dbgs() << "Mapping extracted output " << *LI << " to "
1539  << *Outputs[OutputIdx.getValue()] << "\n");
1540  OutputMappings.insert(std::make_pair(LI, Outputs[OutputIdx.getValue()]));
1541  } else {
1542  Value *Orig = OutputMappings.find(Outputs[OutputIdx.getValue()])->second;
1543  LLVM_DEBUG(dbgs() << "Mapping extracted output " << *Orig << " to "
1544  << *Outputs[OutputIdx.getValue()] << "\n");
1545  OutputMappings.insert(std::make_pair(LI, Orig));
1546  }
1547 }
1548 
1549 bool IROutliner::extractSection(OutlinableRegion &Region) {
1550  SetVector<Value *> ArgInputs, Outputs, SinkCands;
1551  Region.CE->findInputsOutputs(ArgInputs, Outputs, SinkCands);
1552 
1553  assert(Region.StartBB && "StartBB for the OutlinableRegion is nullptr!");
1554  assert(Region.FollowBB && "FollowBB for the OutlinableRegion is nullptr!");
1555  Function *OrigF = Region.StartBB->getParent();
1556  CodeExtractorAnalysisCache CEAC(*OrigF);
1557  Region.ExtractedFunction = Region.CE->extractCodeRegion(CEAC);
1558 
1559  // If the extraction was successful, find the BasicBlock, and reassign the
1560  // OutlinableRegion blocks
1561  if (!Region.ExtractedFunction) {
1562  LLVM_DEBUG(dbgs() << "CodeExtractor failed to outline " << Region.StartBB
1563  << "\n");
1564  Region.reattachCandidate();
1565  return false;
1566  }
1567 
1568  BasicBlock *RewrittenBB = Region.FollowBB->getSinglePredecessor();
1569  Region.StartBB = RewrittenBB;
1570  Region.EndBB = RewrittenBB;
1571 
1572  // The sequences of outlinable regions has now changed. We must fix the
1573  // IRInstructionDataList for consistency. Although they may not be illegal
1574  // instructions, they should not be compared with anything else as they
1575  // should not be outlined in this round. So marking these as illegal is
1576  // allowed.
1577  IRInstructionDataList *IDL = Region.Candidate->front()->IDL;
1578  Instruction *BeginRewritten = &*RewrittenBB->begin();
1579  Instruction *EndRewritten = &*RewrittenBB->begin();
1580  Region.NewFront = new (InstDataAllocator.Allocate()) IRInstructionData(
1581  *BeginRewritten, InstructionClassifier.visit(*BeginRewritten), *IDL);
1582  Region.NewBack = new (InstDataAllocator.Allocate()) IRInstructionData(
1583  *EndRewritten, InstructionClassifier.visit(*EndRewritten), *IDL);
1584 
1585  // Insert the first IRInstructionData of the new region in front of the
1586  // first IRInstructionData of the IRSimilarityCandidate.
1587  IDL->insert(Region.Candidate->begin(), *Region.NewFront);
1588  // Insert the first IRInstructionData of the new region after the
1589  // last IRInstructionData of the IRSimilarityCandidate.
1590  IDL->insert(Region.Candidate->end(), *Region.NewBack);
1591  // Remove the IRInstructionData from the IRSimilarityCandidate.
1592  IDL->erase(Region.Candidate->begin(), std::prev(Region.Candidate->end()));
1593 
1594  assert(RewrittenBB != nullptr &&
1595  "Could not find a predecessor after extraction!");
1596 
1597  // Iterate over the new set of instructions to find the new call
1598  // instruction.
1599  for (Instruction &I : *RewrittenBB)
1600  if (CallInst *CI = dyn_cast<CallInst>(&I)) {
1601  if (Region.ExtractedFunction == CI->getCalledFunction())
1602  Region.Call = CI;
1603  } else if (LoadInst *LI = dyn_cast<LoadInst>(&I))
1604  updateOutputMapping(Region, Outputs.getArrayRef(), LI);
1605  Region.reattachCandidate();
1606  return true;
1607 }
1608 
1609 unsigned IROutliner::doOutline(Module &M) {
1610  // Find the possible similarity sections.
1611  IRSimilarityIdentifier &Identifier = getIRSI(M);
1612  SimilarityGroupList &SimilarityCandidates = *Identifier.getSimilarity();
1613 
1614  // Sort them by size of extracted sections
1615  unsigned OutlinedFunctionNum = 0;
1616  // If we only have one SimilarityGroup in SimilarityCandidates, we do not have
1617  // to sort them by the potential number of instructions to be outlined
1618  if (SimilarityCandidates.size() > 1)
1619  llvm::stable_sort(SimilarityCandidates,
1620  [](const std::vector<IRSimilarityCandidate> &LHS,
1621  const std::vector<IRSimilarityCandidate> &RHS) {
1622  return LHS[0].getLength() * LHS.size() >
1623  RHS[0].getLength() * RHS.size();
1624  });
1625 
1626  DenseSet<unsigned> NotSame;
1627  std::vector<Function *> FuncsToRemove;
1628  // Iterate over the possible sets of similarity.
1629  for (SimilarityGroup &CandidateVec : SimilarityCandidates) {
1630  OutlinableGroup CurrentGroup;
1631 
1632  // Remove entries that were previously outlined
1633  pruneIncompatibleRegions(CandidateVec, CurrentGroup);
1634 
1635  // We pruned the number of regions to 0 to 1, meaning that it's not worth
1636  // trying to outlined since there is no compatible similar instance of this
1637  // code.
1638  if (CurrentGroup.Regions.size() < 2)
1639  continue;
1640 
1641  // Determine if there are any values that are the same constant throughout
1642  // each section in the set.
1643  NotSame.clear();
1644  CurrentGroup.findSameConstants(NotSame);
1645 
1646  if (CurrentGroup.IgnoreGroup)
1647  continue;
1648 
1649  // Create a CodeExtractor for each outlinable region. Identify inputs and
1650  // outputs for each section using the code extractor and create the argument
1651  // types for the Aggregate Outlining Function.
1652  std::vector<OutlinableRegion *> OutlinedRegions;
1653  for (OutlinableRegion *OS : CurrentGroup.Regions) {
1654  // Break the outlinable region out of its parent BasicBlock into its own
1655  // BasicBlocks (see function implementation).
1656  OS->splitCandidate();
1657  std::vector<BasicBlock *> BE = {OS->StartBB};
1658  OS->CE = new (ExtractorAllocator.Allocate())
1659  CodeExtractor(BE, nullptr, false, nullptr, nullptr, nullptr, false,
1660  false, "outlined");
1661  findAddInputsOutputs(M, *OS, NotSame);
1662  if (!OS->IgnoreRegion)
1663  OutlinedRegions.push_back(OS);
1664  else
1665  OS->reattachCandidate();
1666  }
1667 
1668  CurrentGroup.Regions = std::move(OutlinedRegions);
1669 
1670  if (CurrentGroup.Regions.empty())
1671  continue;
1672 
1673  CurrentGroup.collectGVNStoreSets(M);
1674 
1675  if (CostModel)
1676  findCostBenefit(M, CurrentGroup);
1677 
1678  // If we are adhering to the cost model, reattach all the candidates
1679  if (CurrentGroup.Cost >= CurrentGroup.Benefit && CostModel) {
1680  for (OutlinableRegion *OS : CurrentGroup.Regions)
1681  OS->reattachCandidate();
1682  OptimizationRemarkEmitter &ORE = getORE(
1683  *CurrentGroup.Regions[0]->Candidate->getFunction());
1684  ORE.emit([&]() {
1685  IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
1686  OptimizationRemarkMissed R(DEBUG_TYPE, "WouldNotDecreaseSize",
1687  C->frontInstruction());
1688  R << "did not outline "
1689  << ore::NV(std::to_string(CurrentGroup.Regions.size()))
1690  << " regions due to estimated increase of "
1691  << ore::NV("InstructionIncrease",
1692  CurrentGroup.Cost - CurrentGroup.Benefit)
1693  << " instructions at locations ";
1694  interleave(
1695  CurrentGroup.Regions.begin(), CurrentGroup.Regions.end(),
1696  [&R](OutlinableRegion *Region) {
1697  R << ore::NV(
1698  "DebugLoc",
1699  Region->Candidate->frontInstruction()->getDebugLoc());
1700  },
1701  [&R]() { R << " "; });
1702  return R;
1703  });
1704  continue;
1705  }
1706 
1707  LLVM_DEBUG(dbgs() << "Outlining regions with cost " << CurrentGroup.Cost
1708  << " and benefit " << CurrentGroup.Benefit << "\n");
1709 
1710  // Create functions out of all the sections, and mark them as outlined.
1711  OutlinedRegions.clear();
1712  for (OutlinableRegion *OS : CurrentGroup.Regions) {
1713  bool FunctionOutlined = extractSection(*OS);
1714  if (FunctionOutlined) {
1715  unsigned StartIdx = OS->Candidate->getStartIdx();
1716  unsigned EndIdx = OS->Candidate->getEndIdx();
1717  for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
1718  Outlined.insert(Idx);
1719 
1720  OutlinedRegions.push_back(OS);
1721  }
1722  }
1723 
1724  LLVM_DEBUG(dbgs() << "Outlined " << OutlinedRegions.size()
1725  << " with benefit " << CurrentGroup.Benefit
1726  << " and cost " << CurrentGroup.Cost << "\n");
1727 
1728  CurrentGroup.Regions = std::move(OutlinedRegions);
1729 
1730  if (CurrentGroup.Regions.empty())
1731  continue;
1732 
1734  getORE(*CurrentGroup.Regions[0]->Call->getFunction());
1735  ORE.emit([&]() {
1736  IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
1737  OptimizationRemark R(DEBUG_TYPE, "Outlined", C->front()->Inst);
1738  R << "outlined " << ore::NV(std::to_string(CurrentGroup.Regions.size()))
1739  << " regions with decrease of "
1740  << ore::NV("Benefit", CurrentGroup.Benefit - CurrentGroup.Cost)
1741  << " instructions at locations ";
1742  interleave(
1743  CurrentGroup.Regions.begin(), CurrentGroup.Regions.end(),
1744  [&R](OutlinableRegion *Region) {
1745  R << ore::NV("DebugLoc",
1746  Region->Candidate->frontInstruction()->getDebugLoc());
1747  },
1748  [&R]() { R << " "; });
1749  return R;
1750  });
1751 
1752  deduplicateExtractedSections(M, CurrentGroup, FuncsToRemove,
1753  OutlinedFunctionNum);
1754  }
1755 
1756  for (Function *F : FuncsToRemove)
1757  F->eraseFromParent();
1758 
1759  return OutlinedFunctionNum;
1760 }
1761 
1763  CostModel = !NoCostModel;
1764  OutlineFromLinkODRs = EnableLinkOnceODRIROutlining;
1765 
1766  return doOutline(M) > 0;
1767 }
1768 
1769 // Pass Manager Boilerplate
1771 public:
1772  static char ID;
1775  }
1776 
1777  void getAnalysisUsage(AnalysisUsage &AU) const override {
1781  }
1782 
1783  bool runOnModule(Module &M) override;
1784 };
1785 
1787  if (skipModule(M))
1788  return false;
1789 
1790  std::unique_ptr<OptimizationRemarkEmitter> ORE;
1791  auto GORE = [&ORE](Function &F) -> OptimizationRemarkEmitter & {
1792  ORE.reset(new OptimizationRemarkEmitter(&F));
1793  return *ORE.get();
1794  };
1795 
1796  auto GTTI = [this](Function &F) -> TargetTransformInfo & {
1797  return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1798  };
1799 
1800  auto GIRSI = [this](Module &) -> IRSimilarityIdentifier & {
1801  return this->getAnalysis<IRSimilarityIdentifierWrapperPass>().getIRSI();
1802  };
1803 
1804  return IROutliner(GTTI, GIRSI, GORE).run(M);
1805 }
1806 
1808  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
1809 
1811  [&FAM](Function &F) -> TargetTransformInfo & {
1812  return FAM.getResult<TargetIRAnalysis>(F);
1813  };
1814 
1816  [&AM](Module &M) -> IRSimilarityIdentifier & {
1817  return AM.getResult<IRSimilarityAnalysis>(M);
1818  };
1819 
1820  std::unique_ptr<OptimizationRemarkEmitter> ORE;
1822  [&ORE](Function &F) -> OptimizationRemarkEmitter & {
1823  ORE.reset(new OptimizationRemarkEmitter(&F));
1824  return *ORE.get();
1825  };
1826 
1827  if (IROutliner(GTTI, GIRSI, GORE).run(M))
1828  return PreservedAnalyses::none();
1829  return PreservedAnalyses::all();
1830 }
1831 
1832 char IROutlinerLegacyPass::ID = 0;
1833 INITIALIZE_PASS_BEGIN(IROutlinerLegacyPass, "iroutliner", "IR Outliner", false,
1834  false)
1839  false)
1840 
llvm::InstructionCost
Definition: InstructionCost.h:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
IROutliner.h
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:298
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2313
llvm::OptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: DiagnosticInfo.h:729
llvm::AttributeFuncs::mergeAttributesForOutlining
void mergeAttributesForOutlining(Function &Base, const Function &ToMerge)
Merges the functions attributes from ToMerge into function Base.
Definition: Attributes.cpp:2108
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:120
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:64
llvm::IRSimilarity::IRInstructionDataList
Definition: IRSimilarityIdentifier.h:201
llvm::RegionBase::end
iterator end()
Definition: RegionInfo.h:561
llvm::Function::end
iterator end()
Definition: Function.h:780
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
createSwitchStatement
void createSwitchStatement(Module &M, OutlinableGroup &OG, BasicBlock *EndBB, ArrayRef< BasicBlock * > OutputStoreBBs)
Create the switch statement for outlined function to differentiate between all the output blocks.
Definition: IROutliner.cpp:1164
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
llvm::DIBuilder
Definition: DIBuilder.h:41
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
DebugInfoMetadata.h
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:348
llvm::Function
Definition: Function.h:61
llvm::Attribute
Definition: Attributes.h:52
OutlinableGroup::OutputGVNCombinations
DenseSet< ArrayRef< unsigned > > OutputGVNCombinations
A set containing the different GVN store sets needed.
Definition: IROutliner.cpp:80
alignOutputBlockWithAggFunc
static void alignOutputBlockWithAggFunc(OutlinableGroup &OG, OutlinableRegion &Region, BasicBlock *OutputBB, BasicBlock *EndBB, const DenseMap< Value *, Value * > &OutputMappings, std::vector< BasicBlock * > &OutputStoreBBs)
For the outlined section, move needed the StoreInsts for the output registers into their own block.
Definition: IROutliner.cpp:1077
Pass.h
llvm::TargetTransformInfo::getMemoryOpCost
InstructionCost getMemoryOpCost(unsigned Opcode, Type *Src, Align Alignment, unsigned AddressSpace, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, const Instruction *I=nullptr) const
Definition: TargetTransformInfo.cpp:822
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:623
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::IRSimilarityAnalysis
An analysis pass that runs and returns the IRSimilarityIdentifier run on the Module.
Definition: IRSimilarityIdentifier.h:760
llvm::SwitchInst::Create
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3396
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
OutlinableGroup::findSameConstants
void findSameConstants(DenseSet< unsigned > &NotSame)
For the Regions, we look at every Value.
Definition: IROutliner.cpp:341
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:327
OptimizationRemarkEmitter.h
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:214
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
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:492
OutlinableGroup::OutlinedFunctionType
FunctionType * OutlinedFunctionType
The FunctionType for the overall function.
Definition: IROutliner.cpp:66
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1562
IROutlinerLegacyPass::ID
static char ID
Definition: IROutliner.cpp:1772
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
llvm::Function::arg_size
size_t arg_size() const
Definition: Function.h:826
llvm::SetVector::getArrayRef
ArrayRef< T > getArrayRef() const
Definition: SetVector.h:63
llvm::BasicBlock::eraseFromParent
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:129
llvm::IRSimilarity::SimilarityGroup
std::vector< IRSimilarityCandidate > SimilarityGroup
Definition: IRSimilarityIdentifier.h:626
llvm::Optional< unsigned >
llvm::TargetTransformInfo::getCFInstrCost
InstructionCost getCFInstrCost(unsigned Opcode, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const
Definition: TargetTransformInfo.cpp:794
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:267
llvm::IRSimilarity::SimilarityGroupList
std::vector< SimilarityGroup > SimilarityGroupList
Definition: IRSimilarityIdentifier.h:627
llvm::Mangler
Definition: Mangler.h:27
OutlinableGroup::OutlinedFunction
Function * OutlinedFunction
The Function for the collective overall function.
Definition: IROutliner.cpp:68
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::Function::addFnAttr
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.h:255
llvm::cl::ReallyHidden
@ ReallyHidden
Definition: CommandLine.h:144
llvm::IROutlinerPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: IROutliner.cpp:1807
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:203
IROutlinerLegacyPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: IROutliner.cpp:1777
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1198
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:180
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::IRSimilarity::IRSimilarityCandidate::fromGVN
Optional< Value * > fromGVN(unsigned Num)
Finds the Value associate with Num if it exists.
Definition: IRSimilarityIdentifier.h:606
llvm::Value::isSwiftError
bool isSwiftError() const
Return true if this value is a swifterror value.
Definition: Value.cpp:1000
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:288
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:206
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:1790
OutlinableGroup::Regions
std::vector< OutlinableRegion * > Regions
The sections that could be outlined.
Definition: IROutliner.cpp:60
moveFunctionData
static BasicBlock * moveFunctionData(Function &Old, Function &New)
Move each BasicBlock in Old to New.
Definition: IROutliner.cpp:434
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
DEBUG_TYPE
#define DEBUG_TYPE
Definition: IROutliner.cpp:31
llvm::IRSimilarityIdentifierWrapperPass
An analysis pass based on legacy pass manager that runs and returns IRSimilarityIdentifier run on the...
Definition: IRSimilarityIdentifier.h:740
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::AttributeList::getFnAttributes
AttributeSet getFnAttributes() const
The function attributes are returned.
Definition: Attributes.cpp:1383
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
OutlinableGroup::NumAggregateInputs
unsigned NumAggregateInputs
The number of input values in ArgumentTypes.
Definition: IROutliner.cpp:88
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:649
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1518
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:84
false
Definition: StackSlotColoring.cpp:142
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:114
IROutlinerLegacyPass::IROutlinerLegacyPass
IROutlinerLegacyPass()
Definition: IROutliner.cpp:1773
llvm::detail::DenseSetImpl::size
size_type size() const
Definition: DenseSet.h:81
llvm::Instruction
Definition: Instruction.h:45
IROutlinerLegacyPass::runOnModule
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
Definition: IROutliner.cpp:1786
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:899
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
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:522
IR
Statically lint checks LLVM IR
Definition: Lint.cpp:744
findDuplicateOutputBlock
Optional< unsigned > findDuplicateOutputBlock(BasicBlock *OutputBB, ArrayRef< BasicBlock * > OutputStoreBBs)
It is possible that there is a basic block that already performs the same stores.
Definition: IROutliner.cpp:1028
llvm::OutlinableRegion::StartBB
BasicBlock * StartBB
The BasicBlock that contains the starting instruction of the region.
Definition: IROutliner.h:121
llvm::OutlinableRegion::reattachCandidate
void reattachCandidate()
For the contained region, reattach the BasicBlock at the starting and ending instructions of the cont...
Definition: IROutliner.cpp:165
llvm::OutlinableRegion::OutputBlockNum
unsigned OutputBlockNum
The corresponding BasicBlock with the appropriate stores for this OutlinableRegion in the overall fun...
Definition: IROutliner.h:79
llvm::GlobalValue::InternalLinkage
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::StringRef::str
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:245
llvm::None
const NoneType None
Definition: None.h:23
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:548
collectRelevantInstructions
static std::vector< Instruction * > collectRelevantInstructions(Function &F, DenseSet< BasicBlock * > &ExcludeBlocks)
For the given function, find all the nondebug or lifetime instructions, and return them as a vector.
Definition: IROutliner.cpp:1000
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:249
llvm::IRSimilarity::IRSimilarityCandidate::getEndIdx
unsigned getEndIdx() const
Definition: IRSimilarityIdentifier.h:570
llvm::OutlinableRegion::getBenefit
InstructionCost getBenefit(TargetTransformInfo &TTI)
Get the size of the code removed from the region.
Definition: IROutliner.cpp:249
replaceArgumentUses
static void replaceArgumentUses(OutlinableRegion &Region, BasicBlock *OutputBB)
Definition: IROutliner.cpp:918
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::cl::opt< bool >
llvm::OutlinableRegion::ExtractedFunction
Function * ExtractedFunction
The function for the extracted region.
Definition: IROutliner.h:107
llvm::GlobalValue
Definition: GlobalValue.h:44
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:78
llvm::GVN
The core GVN pass object.
Definition: GVN.h:118
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:650
llvm::simple_ilist< IRInstructionData >::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:104
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2369
findExtractedOutputToOverallOutputMapping
static void findExtractedOutputToOverallOutputMapping(OutlinableRegion &Region, ArrayRef< Value * > Outputs)
Create a mapping of the output arguments for the Region to the output arguments of the overall outlin...
Definition: IROutliner.cpp:720
llvm::simple_ilist::erase
iterator erase(iterator I)
Remove a node by iterator; never deletes.
Definition: simple_ilist.h:196
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:1770
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::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3118
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::OutlinableRegion::CE
CodeExtractor * CE
Used to create an outlined function.
Definition: IROutliner.h:101
DIBuilder.h
llvm::DICompileUnit
Compile unit.
Definition: DebugInfoMetadata.h:1317
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:631
IROutlinerLegacyPass
Definition: IROutliner.cpp:1770
fillOverallFunction
static void fillOverallFunction(Module &M, OutlinableGroup &CurrentGroup, std::vector< BasicBlock * > &OutputStoreBBs, std::vector< Function * > &FuncsToRemove)
Fill the new function that will serve as the replacement function for all of the extracted regions of...
Definition: IROutliner.cpp:1220
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:293
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:113
llvm::CmpInst::BAD_ICMP_PREDICATE
@ BAD_ICMP_PREDICATE
Definition: InstrTypes.h:753
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
Mangler.h
OutlinableGroup::Cost
InstructionCost Cost
The number of added instructions needed for the outlining of the Regions.
Definition: IROutliner.cpp:95
llvm::NVPTXISD::Dummy
@ Dummy
Definition: NVPTXISelLowering.h:60
llvm::IROutliner::run
bool run(Module &M)
Definition: IROutliner.cpp:1762
OutlinableGroup
The OutlinableGroup holds all the overarching information for outlining a set of regions that are str...
Definition: IROutliner.cpp:58
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::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:1554
llvm::OutlinableRegion::splitCandidate
void splitCandidate()
For the contained region, split the parent BasicBlock at the starting and ending instructions of the ...
Definition: IROutliner.cpp:129
this
Analysis the ScalarEvolution expression for r is this
Definition: README.txt:8
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:226
llvm::createIROutlinerPass
ModulePass * createIROutlinerPass()
createIROutlinerPass - This pass finds similar code regions and factors those regions out into functi...
Definition: IROutliner.cpp:1841
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:812
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:70
OutlinableGroup::Benefit
InstructionCost Benefit
The number of instructions that will be outlined by extracting Regions.
Definition: IROutliner.cpp:92
llvm::detail::DenseSetImpl::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:520
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::RegionBase::begin
iterator begin()
Definition: RegionInfo.h:560
llvm::TargetTransformInfo::getCmpSelInstrCost
InstructionCost getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy=nullptr, CmpInst::Predicate VecPred=CmpInst::BAD_ICMP_PREDICATE, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, const Instruction *I=nullptr) const
Definition: TargetTransformInfo.cpp:803
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:1415
llvm::CodeExtractor
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
llvm::OutlinableRegion::IgnoreRegion
bool IgnoreRegion
Flag for whether we should not consider this region for extraction.
Definition: IROutliner.h:114
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
OutlinableGroup::IgnoreGroup
bool IgnoreGroup
Flag for whether we should not consider this group of OutlinableRegions for extraction.
Definition: IROutliner.cpp:72
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::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.cpp:148
llvm::Function::begin
iterator begin()
Definition: Function.h:778
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:363
Attributes.h
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:550
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:966
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::OptimizationRemarkEmitterWrapperPass
OptimizationRemarkEmitter legacy analysis pass.
Definition: OptimizationRemarkEmitter.h:146
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1682
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:83
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::Function::getArg
Argument * getArg(unsigned i) const
Definition: Function.h:811
llvm::OutlinableRegion
The OutlinableRegion holds all the information for a specific region, or sequence of instructions.
Definition: IROutliner.h:64
IRSimilarityIdentifier.h
llvm::IRSimilarity::IRSimilarityCandidate::getStartIdx
unsigned getStartIdx() const
Definition: IRSimilarityIdentifier.h:567
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:36
llvm::Function::getFunctionType
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:175
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:470
llvm::TargetTransformInfo::getInstructionCost
InstructionCost getInstructionCost(const Instruction *I, enum TargetCostKind kind) const
Query the cost of a specified instruction.
Definition: TargetTransformInfo.h:225
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:578
llvm::Type::getVoidTy
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:186
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:684
OutlinableGroup::SwiftErrorArgument
Optional< unsigned > SwiftErrorArgument
The argument that needs to be marked with the swifterr attribute.
Definition: IROutliner.cpp:99
llvm::BasicBlock::size
size_t size() const
Definition: BasicBlock.h:306
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::to_string
std::string to_string(const T &Value)
Definition: ScopedPrinter.h:63
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
TargetTransformInfo.h
llvm::detail::DenseSetImpl::erase
bool erase(const ValueT &V)
Definition: DenseSet.h:101
llvm::DISubprogram
Subprogram description.
Definition: DebugInfoMetadata.h:1802
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:926
llvm::IROutliner
This class is a pass that identifies similarity in a Module, extracts instances of the similarity,...
Definition: IROutliner.h:163
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
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
OutlinableGroup::EndBB
BasicBlock * EndBB
The return block for the overall function.
Definition: IROutliner.cpp:75
llvm::IRSimilarity::IRSimilarityIdentifier
This class puts all the pieces of the IRInstructionData, IRInstructionMapper, IRSimilarityCandidate t...
Definition: IRSimilarityIdentifier.h:652
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:528
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::simple_ilist::insert
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
Definition: simple_ilist.h:159
llvm::TargetTransformInfo::TCC_Basic
@ TCC_Basic
The cost of a typical 'add' instruction.
Definition: TargetTransformInfo.h:263
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3206
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:4148
llvm::cl::desc
Definition: CommandLine.h:414
llvm::Region
Definition: RegionInfo.h:889
llvm::SetVector< Value * >
CU
Definition: AArch64AsmBackend.cpp:499
InitializePasses.h
iroutliner
iroutliner
Definition: IROutliner.cpp:1838
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::OutlinableRegion::Candidate
IRSimilarityCandidate * Candidate
Describes the region of code.
Definition: IROutliner.h:66
llvm::Optional::getValue
constexpr const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:282
llvm::DIFile
File.
Definition: DebugInfoMetadata.h:530
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:102
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Function::iterator
BasicBlockListType::iterator iterator
Definition: Function.h:66
llvm::RegionBase::getParent
RegionT * getParent() const
Get the parent of the Region.
Definition: RegionInfo.h:364
Outliner
IR Outliner
Definition: IROutliner.cpp:1838
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38