[IROutliner] Change Prioritization of Outlining to honor cost model

[AndrewLitteken]

Summary

Currently, the IROutliner uses a simple metric to outline the largest amount of IR possible to outline first if it fits the cost model. This is model loses out on smaller blocks of code that have higher reductions in cost that are contained within larger blocks of IR.

This reverses the order, where we calculate all of the costs first, and then reorder and extract items based on the calculated results.

[paquette]

Do you have data on the code size impact of this change?

llvm/include/llvm/Transforms/IPO/IROutliner.h

213

Should this say OutlinableRegion?

259

This seems to have an incorrect comment.

375

why?

llvm/lib/Transforms/IPO/IROutliner.cpp

69

Unnecessary whitespace change?

1279

clang format braces

1287

Might as well pull this above the if to avoid recalculating it.

1311

Probably don't need the variable here?

Just

return any_of(...);

1643

why?

[AndrewLitteken]

Adjusting based on comments, cleaning up the code, and adding an additional check to make sure cost model is still correct when the regions are about to be outlined.

[paquette]

llvm/include/llvm/Transforms/IPO/IROutliner.h

251

Break up run-on?

257

• isCompatibleWithAlreadyOutlinedCode might be a more descriptive name.
• Does this function modify Region? Should it be const?

llvm/lib/Transforms/IPO/IROutliner.cpp

206

is it actually necessary to use this here?

207

Is ID a pointer? Can you loop over it like

for (IRInstructionData *ID ... )

to make that clear?

208

Why is this variable necessary?

1278

Comment?

1282

Comment?

1282

What happens if this is nullptr?

1296

none_of?

1307

Do you need this here?

also you can probably just write

return (std::next(...)->Inst != ID.Inst...) || !InstructionClassifier.visit(ID.Inst);

1639

Would this be better as a SmallVector?

1643–1644

Why not grab this as a reference rather than as a pointer? That would probably reduce the size of this patch significantly.

1682

This could use a comment?

1730

I think you're using the llvm namespace, and std::stable_sort doesn't work with ranges, so I think you can just use

if (...)
  stable_sort(...)

1741

Comment?

1765

Can this use a SmallVector, or will the CodeExtractor not accept that?

[AndrewLitteken]

llvm/lib/Transforms/IPO/IROutliner.cpp

1282

For now, since it's never at the end of a module, this should not be an issue as there is always a branch instruction following, but I will add an assertion.

1307

I would rather keep it like this, the next few patches build on this and becomes more complex when the instruction could be a branch, and it isn't so easy to make it a one liner.

[paquette]

llvm/lib/Transforms/IPO/IROutliner.cpp

1307

SGTM

[AndrewLitteken]

Updating for comments

[paquette]

LGTM

llvm/include/llvm/Transforms/IPO/IROutliner.h

 
 #include "llvm/Analysis/IRSimilarityIdentifier.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueMap.h"
 #include "llvm/Support/InstructionCost.h"
 #include "llvm/Transforms/Utils/CodeExtractor.h"
 #include <set>
 
-struct OutlinableGroup;
-
 namespace llvm {
 using namespace IRSimilarity;
 
 class Module;
 class TargetTransformInfo;
 class OptimizationRemarkEmitter;
+struct OutlinableGroup;
 
 /// The OutlinableRegion holds all the information for a specific region, or
 /// sequence of instructions. This includes what values need to be hoisted to
 /// arguments from the extracted function, inputs and outputs to the region, and
 /// mapping from the extracted function arguments to overall function arguments.
 struct OutlinableRegion {
   /// Describes the region of code.
   IRSimilarityCandidate *Candidate = nullptr;
struct OutlinableRegion {
 
   /// Get the size of the code removed from the region.
   ///
   /// \param [in] TTI - The TargetTransformInfo for the parent function.
   /// \returns the code size of the region
   InstructionCost getBenefit(TargetTransformInfo &TTI);
 };
 
+/// The OutlinableGroup holds all the overarching information for outlining
+/// a set of regions that are structurally similar to one another, such as the
+/// types of the overall function, the output blocks, the sets of stores needed
+/// and a list of the different regions. This information is used in the
+/// deduplication of extracted regions with the same structure.
+struct OutlinableGroup {
+  /// The sections that could be outlined
+  std::vector<OutlinableRegion *> Regions;
+
+  /// The argument types for the function created as the overall function to
+  /// replace the extracted function for each region.
+  std::vector<Type *> ArgumentTypes;
+  /// The FunctionType for the overall function.
+  FunctionType *OutlinedFunctionType = nullptr;
+  /// The Function for the collective overall function.
+  Function *OutlinedFunction = nullptr;
+
+  /// Flag for whether we should not consider this group of OutlinableRegions
+  /// for extraction.
+  bool IgnoreGroup = false;
+
+  /// The return block for the overall function.
+  BasicBlock *EndBB = nullptr;
+
+  /// A set containing the different GVN store sets needed. Each array contains
+  /// a sorted list of the different values that need to be stored into output
+  /// registers.
+  DenseSet<ArrayRef<unsigned>> OutputGVNCombinations;
+
+  /// Flag for whether the \ref ArgumentTypes have been defined after the
+  /// extraction of the first region.
+  bool InputTypesSet = false;
+
+  /// The number of input values in \ref ArgumentTypes.  Anything after this
+  /// index in ArgumentTypes is an output argument.
+  unsigned NumAggregateInputs = 0;
+
+  /// The mapping of the canonical numbering of the values in outlined sections
+  /// to specific arguments.
+  DenseMap<unsigned, unsigned> CanonicalNumberToAggArg;
+
+  /// The number of instructions that will be outlined by extracting \ref
+  /// Regions.
+  InstructionCost Benefit = 0;
+  /// The number of added instructions needed for the outlining of the \ref
+  /// Regions.
+  InstructionCost Cost = 0;
+
+  /// The argument that needs to be marked with the swifterr attribute.  If not
+  /// needed, there is no value.
+  Optional<unsigned> SwiftErrorArgument;
+
+  /// For the \ref Regions, we look at every Value.  If it is a constant,
+  /// we check whether it is the same in Region.
+  ///
+  /// \param [in,out] NotSame contains the global value numbers where the
+  /// constant is not always the same, and must be passed in as an argument.
+  void findSameConstants(DenseSet<unsigned> &NotSame);
+
+  /// For the regions, look at each set of GVN stores needed and account for
+  /// each combination.  Add an argument to the argument types if there is
+  /// more than one combination.
+  ///
+  /// \param [in] M - The module we are outlining from.
+  void collectGVNStoreSets(Module &M);
+};
+
 /// This class is a pass that identifies similarity in a Module, extracts
 /// instances of the similarity, and then consolidating the similar regions
 /// in an effort to reduce code size.  It uses the IRSimilarityIdentifier pass
 /// to identify the similar regions of code, and then extracts the similar
 /// sections into a single function.  See the above for an example as to
 /// how code is extracted and consolidated into a single function.
 class IROutliner {
 public:
   IROutliner(function_ref<TargetTransformInfo &(Function &)> GTTI,
              function_ref<IRSimilarityIdentifier &(Module &)> GIRSI,
              function_ref<OptimizationRemarkEmitter &(Function &)> GORE)
       : getTTI(GTTI), getIRSI(GIRSI), getORE(GORE) {}
   bool run(Module &M);
 
 private:
   /// Find repeated similar code sequences in \p M and outline them into new
   /// Functions.
   ///
   /// \param [in] M - The module to outline from.
   /// \returns The number of Functions created.
   unsigned doOutline(Module &M);
 
   /// Remove all the IRSimilarityCandidates from \p CandidateVec that have
   /// instructions contained in a previously outlined region and put the
   /// remaining regions in \p CurrentGroup.
   ///
   /// \param [in] CandidateVec - List of similarity candidates for regions with
   /// the same similarity structure.
   /// \param [in,out] CurrentGroup - Contains the potential sections to
   /// be outlined.
+  bool
+  compatibleWithOutlined(OutlinableRegion &Region);
+
+  /// Remove all the IRSimilarityCandidates from \p CandidateVec that have
+  /// instructions contained in a previously outlined region and put the
+  /// remaining regions in \p CurrentGroup.
+  ///
+  /// \param [in] CandidateVec - List of similarity candidates for regions with
+  /// the same similarity structure.
+  /// \param [in,out] CurrentGroup - Contains the potential sections to
+  /// be outlined.
   void
   pruneIncompatibleRegions(std::vector<IRSimilarityCandidate> &CandidateVec,
                            OutlinableGroup &CurrentGroup);
 
   /// Create the function based on the overall types found in the current
   /// regions being outlined.
   ///
   /// \param M - The module to outline from.
private:
   function_ref<IRSimilarityIdentifier &(Module &)> getIRSI;
 
   /// The optimization remark emitter for the pass.
   function_ref<OptimizationRemarkEmitter &(Function &)> getORE;
 
   /// The memory allocator used to allocate the CodeExtractors.
   SpecificBumpPtrAllocator<CodeExtractor> ExtractorAllocator;
 
+  /// The memory allocator used to allocate the OutlinableGroups.
+  SpecificBumpPtrAllocator<OutlinableGroup> GroupAllocator;
+  
   /// The memory allocator used to allocate the OutlinableRegions.
   SpecificBumpPtrAllocator<OutlinableRegion> RegionAllocator;
 
   /// The memory allocator used to allocate new IRInstructionData.
   SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
 
   /// Custom InstVisitor to classify different instructions for whether it can
   /// be analyzed for similarity.  This is needed as there may be instruction we

llvm/lib/Transforms/IPO/IROutliner.cpp

 
 // This is a debug option to test small pieces of code to ensure that outlining
 // works correctly.
 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"));
 
-/// The OutlinableGroup holds all the overarching information for outlining
-/// a set of regions that are structurally similar to one another, such as the
-/// types of the overall function, the output blocks, the sets of stores needed
-/// and a list of the different regions. This information is used in the
-/// deduplication of extracted regions with the same structure.
-struct OutlinableGroup {
-  /// The sections that could be outlined
-  std::vector<OutlinableRegion *> Regions;
-
-  /// The argument types for the function created as the overall function to
-  /// replace the extracted function for each region.
-  std::vector<Type *> ArgumentTypes;
-  /// The FunctionType for the overall function.
-  FunctionType *OutlinedFunctionType = nullptr;
-  /// The Function for the collective overall function.
-  Function *OutlinedFunction = nullptr;
-
-  /// Flag for whether we should not consider this group of OutlinableRegions
-  /// for extraction.
-  bool IgnoreGroup = false;
-
-  /// The return block for the overall function.
-  BasicBlock *EndBB = nullptr;
-
-  /// A set containing the different GVN store sets needed. Each array contains
-  /// a sorted list of the different values that need to be stored into output
-  /// registers.
-  DenseSet<ArrayRef<unsigned>> OutputGVNCombinations;
-
-  /// Flag for whether the \ref ArgumentTypes have been defined after the
-  /// extraction of the first region.
-  bool InputTypesSet = false;
-
-  /// The number of input values in \ref ArgumentTypes.  Anything after this
-  /// index in ArgumentTypes is an output argument.
-  unsigned NumAggregateInputs = 0;
-
-  /// The mapping of the canonical numbering of the values in outlined sections
-  /// to specific arguments.
-  DenseMap<unsigned, unsigned> CanonicalNumberToAggArg;
-
-  /// The number of instructions that will be outlined by extracting \ref
-  /// Regions.
-  InstructionCost Benefit = 0;
-  /// The number of added instructions needed for the outlining of the \ref
-  /// Regions.
-  InstructionCost Cost = 0;
-
-  /// The argument that needs to be marked with the swifterr attribute.  If not
-  /// needed, there is no value.
-  Optional<unsigned> SwiftErrorArgument;
-
-  /// For the \ref Regions, we look at every Value.  If it is a constant,
-  /// we check whether it is the same in Region.
-  ///
-  /// \param [in,out] NotSame contains the global value numbers where the
-  /// constant is not always the same, and must be passed in as an argument.
-  void findSameConstants(DenseSet<unsigned> &NotSame);
-
-  /// For the regions, look at each set of GVN stores needed and account for
-  /// each combination.  Add an argument to the argument types if there is
-  /// more than one combination.
-  ///
-  /// \param [in] M - The module we are outlining from.
-  void collectGVNStoreSets(Module &M);
-};
-
 /// Move the contents of \p SourceBB to before the last instruction of \p
 /// TargetBB.
 /// \param SourceBB - the BasicBlock to pull Instructions from.
 /// \param TargetBB - the BasicBlock to put Instruction into.
 static void moveBBContents(BasicBlock &SourceBB, BasicBlock &TargetBB) {
   BasicBlock::iterator BBCurr, BBEnd, BBNext;
   for (BBCurr = SourceBB.begin(), BBEnd = SourceBB.end(); BBCurr != BBEnd;
        BBCurr = BBNext) {
     BBNext = std::next(BBCurr);
     BBCurr->moveBefore(TargetBB, TargetBB.end());
   }
 }
 
 void OutlinableRegion::splitCandidate() {
   assert(!CandidateSplit && "Candidate already split!");
 
+
   if (Candidate->end()->Inst !=
       Candidate->backInstruction()->getNextNonDebugInstruction())
     return;
 
   Instruction *StartInst = (*Candidate->begin()).Inst;
   Instruction *EndInst = (*Candidate->end()).Inst;
   assert(StartInst && EndInst && "Expected a start and end instruction?");
   StartBB = StartInst->getParent();
InstructionCost OutlinableRegion::getBenefit(TargetTransformInfo &TTI) {
   // However, getInstructionCost delegates the code size calculation for
   // arithmetic instructions to getArithmeticInstrCost in
   // include/Analysis/TargetTransformImpl.h, where it always estimates that the
   // code size for a division and remainder instruction to be equal to 4, and
   // everything else to 1.  This is not an accurate representation of the
   // division instruction for targets that have a native division instruction.
   // To be overly conservative, we only add 1 to the number of instructions for
   // each division instruction.
   for (Instruction &I : *StartBB) {
     switch (I.getOpcode()) {
     case Instruction::FDiv:
     case Instruction::FRem:
     case Instruction::SDiv:
     case Instruction::SRem:
     case Instruction::UDiv:
     case Instruction::URem:
       Benefit += 1;
       break;
     default:
void IROutliner::deduplicateExtractedSections(
   }
 
   // Create a switch statement to handle the different output schemes.
   createSwitchStatement(M, CurrentGroup, CurrentGroup.EndBB, OutputStoreBBs);
 
   OutlinedFunctionNum++;
 }
 
+bool IROutliner::compatibleWithOutlined(OutlinableRegion &Region) {
+  IRSimilarityCandidate *IRSC = Region.Candidate;
+  unsigned StartIdx = IRSC->getStartIdx();
+  unsigned EndIdx = IRSC->getEndIdx();
+
+  for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
+    if (Outlined.contains(Idx)) {
+      return false;
+    }
+  
+  if (Region.Candidate->end()->Inst !=
+      Region.Candidate->backInstruction()->getNextNonDebugInstruction()) {
+    IRInstructionDataList *IDL = Region.Candidate->front()->IDL;
+    Instruction *NewEndInst =
+        Region.Candidate->backInstruction()->getNextNonDebugInstruction();
+    IRInstructionData *NewEndIRID = new (InstDataAllocator.Allocate())
+        IRInstructionData(*NewEndInst,
+                          InstructionClassifier.visit(*NewEndInst), *IDL);
+
+    // Insert the first IRInstructionData of the new region after the
+    // last IRInstructionData of the IRSimilarityCandidate.
+    IDL->insert(Region.Candidate->end(), *NewEndIRID);
+  }    
+
+  bool BadInst = any_of(*IRSC, [this](IRInstructionData &ID) {
+    // We check if there is a discrepancy between the InstructionDataList
+    // and the actual next instruction in the module.  If there is, it means
+    // that an extra instruction was added, likely by the CodeExtractor.
+
+    // Since we do not have any similarity data about this particular
+    // instruction, we cannot confidently outline it, and must discard this
+    // candidate.
+    if (std::next(ID.getIterator())->Inst !=
+        ID.Inst->getNextNonDebugInstruction())
+      return true;
+    return !this->InstructionClassifier.visit(ID.Inst);
+  });
+
+  return !BadInst;
+}
+
 void IROutliner::pruneIncompatibleRegions(
     std::vector<IRSimilarityCandidate> &CandidateVec,
     OutlinableGroup &CurrentGroup) {
   bool PreviouslyOutlined;
 
   // Sort from beginning to end, so the IRSimilarityCandidates are in order.
   stable_sort(CandidateVec, [](const IRSimilarityCandidate &LHS,
                                const IRSimilarityCandidate &RHS) {
if (SimilarityCandidates.size() > 1)
     llvm::stable_sort(SimilarityCandidates,
                       [](const std::vector<IRSimilarityCandidate> &LHS,
                          const std::vector<IRSimilarityCandidate> &RHS) {
                         return LHS[0].getLength() * LHS.size() >
                                RHS[0].getLength() * RHS.size();
                       });
 
   DenseSet<unsigned> NotSame;
-  std::vector<Function *> FuncsToRemove;
+  std::vector<OutlinableGroup *> NegativeCostGroups;
+  std::vector<OutlinableRegion *> OutlinedRegions;
   // Iterate over the possible sets of similarity.
   for (SimilarityGroup &CandidateVec : SimilarityCandidates) {
-    OutlinableGroup CurrentGroup;
+    OutlinableGroup *CurrentGroup =
+        new (GroupAllocator.Allocate()) OutlinableGroup;
 
     // Remove entries that were previously outlined
-    pruneIncompatibleRegions(CandidateVec, CurrentGroup);
+    pruneIncompatibleRegions(CandidateVec, *CurrentGroup);
 
     // We pruned the number of regions to 0 to 1, meaning that it's not worth
     // trying to outlined since there is no compatible similar instance of this
     // code.
-    if (CurrentGroup.Regions.size() < 2)
+    if (CurrentGroup->Regions.size() < 2)
       continue;
 
     // Determine if there are any values that are the same constant throughout
     // each section in the set.
     NotSame.clear();
-    CurrentGroup.findSameConstants(NotSame);
+    CurrentGroup->findSameConstants(NotSame);
 
-    if (CurrentGroup.IgnoreGroup)
+    if (CurrentGroup->IgnoreGroup)
       continue;
 
     // Create a CodeExtractor for each outlinable region. Identify inputs and
     // outputs for each section using the code extractor and create the argument
     // types for the Aggregate Outlining Function.
-    std::vector<OutlinableRegion *> OutlinedRegions;
-    for (OutlinableRegion *OS : CurrentGroup.Regions) {
+    OutlinedRegions.clear();
+    for (OutlinableRegion *OS : CurrentGroup->Regions) {
       // Break the outlinable region out of its parent BasicBlock into its own
       // BasicBlocks (see function implementation).
       OS->splitCandidate();
       if (!OS->CandidateSplit)
         continue;
 
       std::vector<BasicBlock *> BE = {OS->StartBB};
       OS->CE = new (ExtractorAllocator.Allocate())
           CodeExtractor(BE, nullptr, false, nullptr, nullptr, nullptr, false,
                         false, "outlined");
       findAddInputsOutputs(M, *OS, NotSame);
       if (!OS->IgnoreRegion)
         OutlinedRegions.push_back(OS);
       else
         OS->reattachCandidate();
     }
 
-    CurrentGroup.Regions = std::move(OutlinedRegions);
+    CurrentGroup->Regions = std::move(OutlinedRegions);
 
-    if (CurrentGroup.Regions.empty())
+    if (CurrentGroup->Regions.empty())
       continue;
 
-    CurrentGroup.collectGVNStoreSets(M);
+    CurrentGroup->collectGVNStoreSets(M);
 
     if (CostModel)
-      findCostBenefit(M, CurrentGroup);
+      findCostBenefit(M, *CurrentGroup);
 
     // If we are adhering to the cost model, reattach all the candidates
-    if (CurrentGroup.Cost >= CurrentGroup.Benefit && CostModel) {
-      for (OutlinableRegion *OS : CurrentGroup.Regions)
+    if (CurrentGroup->Cost >= CurrentGroup->Benefit && CostModel) {
+      for (OutlinableRegion *OS : CurrentGroup->Regions)
         OS->reattachCandidate();
       OptimizationRemarkEmitter &ORE = getORE(
-          *CurrentGroup.Regions[0]->Candidate->getFunction());
+          *CurrentGroup->Regions[0]->Candidate->getFunction());
       ORE.emit([&]() {
-        IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
+        IRSimilarityCandidate *C = CurrentGroup->Regions[0]->Candidate;
         OptimizationRemarkMissed R(DEBUG_TYPE, "WouldNotDecreaseSize",
                                    C->frontInstruction());
         R << "did not outline "
-          << ore::NV(std::to_string(CurrentGroup.Regions.size()))
+          << ore::NV(std::to_string(CurrentGroup->Regions.size()))
           << " regions due to estimated increase of "
           << ore::NV("InstructionIncrease",
-                     CurrentGroup.Cost - CurrentGroup.Benefit)
+                     CurrentGroup->Cost - CurrentGroup->Benefit)
           << " instructions at locations ";
         interleave(
-            CurrentGroup.Regions.begin(), CurrentGroup.Regions.end(),
+            CurrentGroup->Regions.begin(), CurrentGroup->Regions.end(),
             [&R](OutlinableRegion *Region) {
               R << ore::NV(
                   "DebugLoc",
                   Region->Candidate->frontInstruction()->getDebugLoc());
             },
             [&R]() { R << " "; });
         return R;
       });
       continue;
     }
 
+    NegativeCostGroups.push_back(CurrentGroup);
+    for (OutlinableRegion *OS : CurrentGroup->Regions)
+      OS->reattachCandidate();
+  }
+
+  ExtractorAllocator.DestroyAll();
+
+  if (NegativeCostGroups.size() > 1)
+    llvm::stable_sort(NegativeCostGroups,
+                      [](const OutlinableGroup *LHS,
+                         const OutlinableGroup *RHS) {
+                        return LHS->Benefit - LHS->Cost > RHS->Benefit - RHS->Cost;
+                      });
+
+  std::vector<Function *> FuncsToRemove;
+  for (OutlinableGroup *CG : NegativeCostGroups) {
+    OutlinableGroup &CurrentGroup = *CG;
+
+    OutlinedRegions.clear();
+    for (OutlinableRegion *Region : CurrentGroup.Regions) {
+      if(!compatibleWithOutlined(*Region))
+        continue;
+      Region->splitCandidate();
+      if (!Region->CandidateSplit)
+        continue;
+      OutlinedRegions.push_back(Region);
+    }
+
+    CurrentGroup.Regions = std::move(OutlinedRegions);
+    if (CurrentGroup.Regions.size() < 2) {
+      for (OutlinableRegion *R : CurrentGroup.Regions)
+        R->reattachCandidate();
+      continue;
+    }
+    
     LLVM_DEBUG(dbgs() << "Outlining regions with cost " << CurrentGroup.Cost
                       << " and benefit " << CurrentGroup.Benefit << "\n");
 
     // Create functions out of all the sections, and mark them as outlined.
     OutlinedRegions.clear();
     for (OutlinableRegion *OS : CurrentGroup.Regions) {
+      std::vector<BasicBlock *> BE = {OS->StartBB};
+      OS->CE = new (ExtractorAllocator.Allocate())
+          CodeExtractor(BE, nullptr, false, nullptr, nullptr, nullptr, false,
+                        false, "outlined");
       bool FunctionOutlined = extractSection(*OS);
       if (FunctionOutlined) {
         unsigned StartIdx = OS->Candidate->getStartIdx();
         unsigned EndIdx = OS->Candidate->getEndIdx();
         for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
           Outlined.insert(Idx);
 
         OutlinedRegions.push_back(OS);
       }
     }
 
     LLVM_DEBUG(dbgs() << "Outlined " << OutlinedRegions.size()
                       << " with benefit " << CurrentGroup.Benefit
                       << " and cost " << CurrentGroup.Cost << "\n");
 
     CurrentGroup.Regions = std::move(OutlinedRegions);
 
-    if (CurrentGroup.Regions.empty())
-      continue;
-
     OptimizationRemarkEmitter &ORE =
         getORE(*CurrentGroup.Regions[0]->Call->getFunction());
     ORE.emit([&]() {
       IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
       OptimizationRemark R(DEBUG_TYPE, "Outlined", C->front()->Inst);
       R << "outlined " << ore::NV(std::to_string(CurrentGroup.Regions.size()))
         << " regions with decrease of "
         << ore::NV("Benefit", CurrentGroup.Benefit - CurrentGroup.Cost)

llvm/test/Transforms/IROutliner/opt-remarks.ll

 ; RUN: opt -S -verify -iroutliner -o /dev/null \ 
 ; RUN: -pass-remarks=iroutliner -pass-remarks-missed=iroutliner < %s  \
 ; RUN: 2>&1 | FileCheck -check-prefix=CHECK %s
 ; RUN: opt -S -verify -iroutliner -o /dev/null  \
 ; RUN:  -pass-remarks-output=%t < %s
 ; RUN: cat %t | FileCheck -check-prefix=YAML %s
 
 ; CHECK: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 12 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
 ; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 5 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
-; CHECK-NEXT: remark: <unknown>:0:0: outlined 2 regions with decrease of 2 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 0 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
 ; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 10 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 1 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
 ; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 11 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
 ; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 12 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 2 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 3 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
 ; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 13 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 4 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
 ; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 14 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 5 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
 ; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 10 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
 ; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 11 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 6 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 7 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
 ; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 17 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
 ; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 13 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT: remark: <unknown>:0:0: did not outline 2 regions due to estimated increase of 8 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT: remark: <unknown>:0:0: outlined 2 regions with decrease of 2 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
 
 ; YAML: --- !Missed
 ; YAML-NEXT: Pass:            iroutliner
 ; YAML-NEXT: Name:            WouldNotDecreaseSize
 ; YAML-NEXT: Function:        function3
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'did not outline '
 ; YAML-NEXT:   - String:          '2'

 ; YAML-NEXT:   - String:          '2'
 ; YAML-NEXT:   - String:          ' regions due to estimated increase of '
 ; YAML-NEXT:   - InstructionIncrease: '5'
 ; YAML-NEXT:   - String:          ' instructions at locations '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT:   - String:          ' '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT: ...
-; YAML-NEXT: --- !Passed
+; YAML-NEXT: --- !Missed
 ; YAML-NEXT: Pass:            iroutliner
-; YAML-NEXT: Name:            Outlined
-; YAML-NEXT: Function:        function3.outlined
+; YAML-NEXT: Name:            WouldNotDecreaseSize
+; YAML-NEXT: Function:        function3
 ; YAML-NEXT: Args:
-; YAML-NEXT:   - String:          'outlined '
+; YAML-NEXT:   - String:          'did not outline '
 ; YAML-NEXT:   - String:          '2'
-; YAML-NEXT:   - String:          ' regions with decrease of '
-; YAML-NEXT:   - Benefit:         '2'
+; YAML-NEXT:   - String:          ' regions due to estimated increase of '
+; YAML-NEXT:   - InstructionIncrease: '0'
 ; YAML-NEXT:   - String:          ' instructions at locations '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT:   - String:          ' '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT: ...
 ; YAML-NEXT: --- !Missed
 ; YAML-NEXT: Pass:            iroutliner
 ; YAML-NEXT: Name:            WouldNotDecreaseSize
 ; YAML-NEXT: Function:        function1
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'did not outline '
 ; YAML-NEXT:   - String:          '2'
 ; YAML-NEXT:   - String:          ' regions due to estimated increase of '
 ; YAML-NEXT:   - InstructionIncrease: '10'
 ; YAML-NEXT:   - String:          ' instructions at locations '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT:   - String:          ' '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT: ...
 ; YAML-NEXT: --- !Missed
 ; YAML-NEXT: Pass:            iroutliner
 ; YAML-NEXT: Name:            WouldNotDecreaseSize
+; YAML-NEXT: Function:        function3
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'did not outline '
+; YAML-NEXT:   - String:          '2'
+; YAML-NEXT:   - String:          ' regions due to estimated increase of '
+; YAML-NEXT:   - InstructionIncrease: '1'
+; YAML-NEXT:   - String:          ' instructions at locations '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT:   - String:          ' '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Missed
+; YAML-NEXT: Pass:            iroutliner
+; YAML-NEXT: Name:            WouldNotDecreaseSize
 ; YAML-NEXT: Function:        function1
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'did not outline '
 ; YAML-NEXT:   - String:          '2'
 ; YAML-NEXT:   - String:          ' regions due to estimated increase of '
 ; YAML-NEXT:   - InstructionIncrease: '11'
 ; YAML-NEXT:   - String:          ' instructions at locations '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'

 ; YAML-NEXT:   - String:          ' instructions at locations '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT:   - String:          ' '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT: ...
 ; YAML-NEXT: --- !Missed
 ; YAML-NEXT: Pass:            iroutliner
 ; YAML-NEXT: Name:            WouldNotDecreaseSize
+; YAML-NEXT: Function:        function3
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'did not outline '
+; YAML-NEXT:   - String:          '2'
+; YAML-NEXT:   - String:          ' regions due to estimated increase of '
+; YAML-NEXT:   - InstructionIncrease: '2'
+; YAML-NEXT:   - String:          ' instructions at locations '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT:   - String:          ' '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Missed
+; YAML-NEXT: Pass:            iroutliner
+; YAML-NEXT: Name:            WouldNotDecreaseSize
+; YAML-NEXT: Function:        function3
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'did not outline '
+; YAML-NEXT:   - String:          '2'
+; YAML-NEXT:   - String:          ' regions due to estimated increase of '
+; YAML-NEXT:   - InstructionIncrease: '3'
+; YAML-NEXT:   - String:          ' instructions at locations '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT:   - String:          ' '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Missed
+; YAML-NEXT: Pass:            iroutliner
+; YAML-NEXT: Name:            WouldNotDecreaseSize
 ; YAML-NEXT: Function:        function1
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'did not outline '
 ; YAML-NEXT:   - String:          '2'
 ; YAML-NEXT:   - String:          ' regions due to estimated increase of '
 ; YAML-NEXT:   - InstructionIncrease: '13'
 ; YAML-NEXT:   - String:          ' instructions at locations '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT:   - String:          ' '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT: ...
 ; YAML-NEXT: --- !Missed
 ; YAML-NEXT: Pass:            iroutliner
 ; YAML-NEXT: Name:            WouldNotDecreaseSize
+; YAML-NEXT: Function:        function3
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'did not outline '
+; YAML-NEXT:   - String:          '2'
+; YAML-NEXT:   - String:          ' regions due to estimated increase of '
+; YAML-NEXT:   - InstructionIncrease: '4'
+; YAML-NEXT:   - String:          ' instructions at locations '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT:   - String:          ' '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Missed
+; YAML-NEXT: Pass:            iroutliner
+; YAML-NEXT: Name:            WouldNotDecreaseSize
 ; YAML-NEXT: Function:        function1
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'did not outline '
 ; YAML-NEXT:   - String:          '2'
 ; YAML-NEXT:   - String:          ' regions due to estimated increase of '
 ; YAML-NEXT:   - InstructionIncrease: '14'
 ; YAML-NEXT:   - String:          ' instructions at locations '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT:   - String:          ' '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT: ...
 ; YAML-NEXT: --- !Missed
 ; YAML-NEXT: Pass:            iroutliner
 ; YAML-NEXT: Name:            WouldNotDecreaseSize
+; YAML-NEXT: Function:        function3
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'did not outline '
+; YAML-NEXT:   - String:          '2'
+; YAML-NEXT:   - String:          ' regions due to estimated increase of '
+; YAML-NEXT:   - InstructionIncrease: '5'
+; YAML-NEXT:   - String:          ' instructions at locations '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT:   - String:          ' '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Missed
+; YAML-NEXT: Pass:            iroutliner
+; YAML-NEXT: Name:            WouldNotDecreaseSize
 ; YAML-NEXT: Function:        function1
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'did not outline '
 ; YAML-NEXT:   - String:          '2'
 ; YAML-NEXT:   - String:          ' regions due to estimated increase of '
 ; YAML-NEXT:   - InstructionIncrease: '10'
 ; YAML-NEXT:   - String:          ' instructions at locations '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'

 ; YAML-NEXT:   - String:          ' instructions at locations '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT:   - String:          ' '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT: ...
 ; YAML-NEXT: --- !Missed
 ; YAML-NEXT: Pass:            iroutliner
 ; YAML-NEXT: Name:            WouldNotDecreaseSize
+; YAML-NEXT: Function:        function3
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'did not outline '
+; YAML-NEXT:   - String:          '2'
+; YAML-NEXT:   - String:          ' regions due to estimated increase of '
+; YAML-NEXT:   - InstructionIncrease: '6'
+; YAML-NEXT:   - String:          ' instructions at locations '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT:   - String:          ' '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Missed
+; YAML-NEXT: Pass:            iroutliner
+; YAML-NEXT: Name:            WouldNotDecreaseSize
+; YAML-NEXT: Function:        function3
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'did not outline '
+; YAML-NEXT:   - String:          '2'
+; YAML-NEXT:   - String:          ' regions due to estimated increase of '
+; YAML-NEXT:   - InstructionIncrease: '7'
+; YAML-NEXT:   - String:          ' instructions at locations '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT:   - String:          ' '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Missed
+; YAML-NEXT: Pass:            iroutliner
+; YAML-NEXT: Name:            WouldNotDecreaseSize
 ; YAML-NEXT: Function:        function1
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'did not outline '
 ; YAML-NEXT:   - String:          '2'
 ; YAML-NEXT:   - String:          ' regions due to estimated increase of '
 ; YAML-NEXT:   - InstructionIncrease: '17'
 ; YAML-NEXT:   - String:          ' instructions at locations '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'

 ; YAML-NEXT:   - String:          '2'
 ; YAML-NEXT:   - String:          ' regions due to estimated increase of '
 ; YAML-NEXT:   - InstructionIncrease: '13'
 ; YAML-NEXT:   - String:          ' instructions at locations '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT:   - String:          ' '
 ; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
 ; YAML-NEXT: ...
+; YAML-NEXT: --- !Missed
+; YAML-NEXT: Pass:            iroutliner
+; YAML-NEXT: Name:            WouldNotDecreaseSize
+; YAML-NEXT: Function:        function3
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'did not outline '
+; YAML-NEXT:   - String:          '2'
+; YAML-NEXT:   - String:          ' regions due to estimated increase of '
+; YAML-NEXT:   - InstructionIncrease: '8'
+; YAML-NEXT:   - String:          ' instructions at locations '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT:   - String:          ' '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Passed
+; YAML-NEXT: Pass:            iroutliner
+; YAML-NEXT: Name:            Outlined
+; YAML-NEXT: Function:        function3.outlined
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'outlined '
+; YAML-NEXT:   - String:          '2'
+; YAML-NEXT:   - String:          ' regions with decrease of '
+; YAML-NEXT:   - Benefit:         '2'
+; YAML-NEXT:   - String:          ' instructions at locations '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT:   - String:          ' '
+; YAML-NEXT:   - DebugLoc:        '<UNKNOWN LOCATION>'
+; YAML-NEXT: ...
 
 define void @function1() #0 {
 entry:
   %a = alloca i32, align 4
   %b = alloca i32, align 4
   %output = alloca i32, align 4
   %result = alloca i32, align 4
   store i32 2, i32* %a, align 4

llvm/test/Transforms/IROutliner/outlining-bitcasts.ll

 ; CHECK-NEXT:    [[LT_CAST:%.*]] = bitcast i32* [[D]] to i8*
 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 -1, i8* [[LT_CAST]])
 ; CHECK-NEXT:    ret void
 ;
 ;
 ; CHECK-LABEL: @outline_bitcast_base2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[D:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    call void @outlined_ir_func_1(i32* [[D]], i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]])
+; CHECK-NEXT:    [[X:%.*]] = bitcast i32* [[D]] to i8*
+; CHECK-NEXT:    [[AL:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[BL:%.*]] = add i32 [[B]], [[A]]
+; CHECK-NEXT:    [[CL:%.*]] = add i32 [[B]], [[C:%.*]]
 ; CHECK-NEXT:    [[BUFFER:%.*]] = mul i32 [[A]], [[B]]
 ; CHECK-NEXT:    [[Y:%.*]] = bitcast i32* [[D]] to i8*
 ; CHECK-NEXT:    [[AM:%.*]] = add i32 [[A]], [[B]]
 ; CHECK-NEXT:    [[BM:%.*]] = add i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[CM:%.*]] = add i32 [[B]], [[C]]
 ; CHECK-NEXT:    [[LT_CAST1:%.*]] = bitcast i32* [[D]] to i8*
 ; CHECK-NEXT:    call void @llvm.lifetime.start.p0i8(i64 -1, i8* [[LT_CAST1]])
 ; CHECK-NEXT:    [[LT_CAST:%.*]] = bitcast i32* [[D]] to i8*
 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 -1, i8* [[LT_CAST]])
 ; CHECK-NEXT:    ret void
 ;
 ;
-; CHECK: @outlined_ir_func_0(i32* [[TMP0:%.*]], i32* [[TMP1:%.*]], i32* [[TMP2:%.*]], i32* [[TMP3:%.*]])
+; CHECK-LABEL: @outlined_ir_func_0(
+; CHECK-NEXT:  newFuncRoot:
+; CHECK-NEXT:    br label [[ENTRY_TO_OUTLINE:%.*]]
+; CHECK:       entry_after_outline.exitStub:
+; CHECK-NEXT:    ret void
 ; CHECK:       entry_to_outline:
 ; CHECK-NEXT:    store i32 2, i32* [[TMP0:%.*]], align 4
 ; CHECK-NEXT:    store i32 3, i32* [[TMP1:%.*]], align 4
 ; CHECK-NEXT:    store i32 4, i32* [[TMP2:%.*]], align 4
 ; CHECK-NEXT:    [[X:%.*]] = bitcast i32* [[TMP3:%.*]] to i8*
 ; CHECK-NEXT:    [[AL:%.*]] = load i32, i32* [[TMP0]], align 4
 ; CHECK-NEXT:    [[BL:%.*]] = load i32, i32* [[TMP1]], align 4
 ; CHECK-NEXT:    [[CL:%.*]] = load i32, i32* [[TMP2]], align 4
 ; CHECK-NEXT:    br label [[ENTRY_AFTER_OUTLINE_EXITSTUB:%.*]]
 ;
-;
-; CHECK: @outlined_ir_func_1(i32* [[TMP0:%.*]], i32 [[TMP1:%.*]], i32 [[TMP2:%.*]], i32 [[TMP3:%.*]])
-; CHECK:       entry_to_outline:
-; CHECK-NEXT:    [[X:%.*]] = bitcast i32* [[TMP0]] to i8*
-; CHECK-NEXT:    [[AL:%.*]] = add i32 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    [[BL:%.*]] = add i32 [[TMP2]], [[TMP1]]
-; CHECK-NEXT:    [[CL:%.*]] = add i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    br label [[ENTRY_AFTER_OUTLINE_EXITSTUB:%.*]]
-;