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