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