[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

193

This seems to have an incorrect comment.

214

Should this say OutlinableRegion?

307

why?

llvm/lib/Transforms/IPO/IROutliner.cpp

136

Unnecessary whitespace change?

1354

clang format braces

1362

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

1386

Probably don't need the variable here?

Just

return any_of(...);

1719

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

185

Break up run-on?

191

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

llvm/lib/Transforms/IPO/IROutliner.cpp

277

is it actually necessary to use this here?

278

Is ID a pointer? Can you loop over it like

for (IRInstructionData *ID ... )

to make that clear?

279

Why is this variable necessary?

1353

Comment?

1357

Comment?

1357

What happens if this is nullptr?

1371

none_of?

1382

Do you need this here?

also you can probably just write

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

1711

Would this be better as a SmallVector?

1719

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

1760

This could use a comment?

1807

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(...)

1818

Comment?

1857

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

[AndrewLitteken]

llvm/lib/Transforms/IPO/IROutliner.cpp

1357

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.

1382

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

1382

SGTM

[AndrewLitteken]

Updating for comments

[paquette]

LGTM

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

 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);
 
+  /// Check whether an OutlinableRegion is incompatible with code already
+  /// outlined, that is whether there are overlapping instructions, code that
+  /// has not been recorded added to the instructions.
+  ///
+  /// \param [in] Region - The OutlinableRegion to check for conflicts with
+  /// already outlined code.
+  /// \returns whether the region can safely 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.
   /// \param [in,out] CG - The OutlinableGroup for the regions to be outlined.
   /// \param [in] FunctionNameSuffix - How many functions have we previously
   /// created.
   /// \returns the newly created function.
   Function *createFunction(Module &M, OutlinableGroup &CG,
                            unsigned FunctionNameSuffix);
 
   /// Identify the needed extracted inputs in a section, and add to the overall
   /// function if needed.
   ///
   /// \param [in] M - The module to outline from.
   /// \param [in,out] Region - The region to be extracted.
   /// \param [in] NotSame - The global value numbers of the Values in the region
   /// that do not have the same Constant in each strucutrally similar region.
private:
   /// IRSimilarityIdentifier lambda to retrieve IRSimilarityIdentifier.
   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 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
   /// can identify as having similarity, but are more complicated to outline.
   struct InstructionAllowed : public InstVisitor<InstructionAllowed, bool> {

llvm/lib/Transforms/IPO/IROutliner.cpp

for (BBCurr = SourceBB.begin(), BBEnd = SourceBB.end(); BBCurr != BBEnd;
     BBNext = std::next(BBCurr);
     BBCurr->moveBefore(TargetBB, TargetBB.end());
   }
 }
 
 void OutlinableRegion::splitCandidate() {
   assert(!CandidateSplit && "Candidate already split!");
 
   Instruction *EndInst = (*Candidate->end()).Inst;
   assert(EndInst && "Expected an end instruction?");
 
   // We check if the current instruction following the last instruction in the
   // region is the same as the recorded instruction following the last
   // instruction, if they do not match, there could be problems in rewriting
   // the program after outlining, so we ignore it.
   if (EndInst != Candidate->backInstruction()->getNextNonDebugInstruction())
     return;
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) {
+  for (IRInstructionData &ID : *this->Candidate) {
+    Instruction &I = *ID.Inst;
+    InstructionCost IndividualBen;
     switch (I.getOpcode()) {
     case Instruction::FDiv:
     case Instruction::FRem:
     case Instruction::SDiv:
     case Instruction::SRem:
     case Instruction::UDiv:
     case Instruction::URem:
-      Benefit += 1;
+      IndividualBen = 1;
       break;
     default:
-      Benefit += TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);
+      IndividualBen =
+          TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);
       break;
     }
+    Benefit += IndividualBen;
   }
 
   return Benefit;
 }
 
 /// Find whether \p Region matches the global value numbering to Constant
 /// mapping found so far.
 ///
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;
+
+  Instruction *RealEndInstruction =
+      Region.Candidate->backInstruction()->getNextNonDebugInstruction();
+  if (Region.Candidate->end()->Inst != RealEndInstruction) {
+    IRInstructionDataList *IDL = Region.Candidate->front()->IDL;
+    Instruction *NewEndInst = RealEndInstruction;
+    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);
+  }
+
+  return !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);
+  });
+}
+
 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) {
     return LHS.getStartIdx() < RHS.getStartIdx();
unsigned IROutliner::doOutline(Module &M) {
   // to sort them by the potential number of instructions to be outlined
   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();
                       });
+  // Creating OutlinableGroups for each SimilarityCandidate to be used in
+  // each of the following for loops to avoid making an allocator.
+  std::vector<OutlinableGroup> PotentialGroups(SimilarityCandidates.size());
 
   DenseSet<unsigned> NotSame;
-  std::vector<Function *> FuncsToRemove;
+  std::vector<OutlinableGroup *> NegativeCostGroups;
+  std::vector<OutlinableRegion *> OutlinedRegions;
   // Iterate over the possible sets of similarity.
+  unsigned PotentialGroupIdx = 0;
   for (SimilarityGroup &CandidateVec : SimilarityCandidates) {
-    OutlinableGroup CurrentGroup;
+    OutlinableGroup *CurrentGroup = &PotentialGroups[PotentialGroupIdx++];
 
     // 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();
 
       // There's a chance that when the region is split, extra instructions are
       // added changing the possibility of outlining, and it is no longer viable
       // to be split, so we ignore it.
       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)
-        OS->reattachCandidate();
-      OptimizationRemarkEmitter &ORE = getORE(
-          *CurrentGroup.Regions[0]->Candidate->getFunction());
+    // If we are adhering to the cost model, skip those groups where the cost
+    // outweighs the benefits.
+    if (CurrentGroup->Cost >= CurrentGroup->Benefit && CostModel) {
+      OptimizationRemarkEmitter &ORE =
+          getORE(*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);
+  }
+
+  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;
+      OutlinedRegions.push_back(Region);
+    }
+
+    if (OutlinedRegions.size() < 2)
+      continue;
+
+    // Reestimate the cost and benefit of the OutlinableGroup. Continue only if
+    // we are still outlining enough regions to make up for the added cost.
+    CurrentGroup.Regions = std::move(OutlinedRegions);
+    if (CostModel) {
+      CurrentGroup.Benefit = 0;
+      CurrentGroup.Cost = 0;
+      findCostBenefit(M, CurrentGroup);
+      if (CurrentGroup.Cost >= CurrentGroup.Benefit)
+        continue;
+    }
+    OutlinedRegions.clear();
+    for (OutlinableRegion *Region : CurrentGroup.Regions) {
+      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 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 12 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 14 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 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: 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 6 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 1 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 11 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 2 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 12 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 13 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 3 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 4 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 14 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 5 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 15 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 6 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 11 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 12 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 7 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 8 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 18 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 14 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: did not outline 2 regions due to estimated increase of 9 instructions at locations <UNKNOWN LOCATION> <UNKNOWN LOCATION>
+; CHECK-NEXT:  <unknown>:0:0: outlined 2 regions with decrease of 1 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:          ' regions due to estimated increase of '
-; YAML-NEXT:   - InstructionIncrease: '12'
+; 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: '5'
+; 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: --- !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: 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: '10'
+; 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:          ' '
 ; 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:        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: '12'
 ; 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: '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:        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:   - InstructionIncrease: '15'
+; 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: --- !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:   - InstructionIncrease: '12'
+; 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:        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: --- !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:   - InstructionIncrease: '18'
+; 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: '9'
+; 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:         '1'
 ; 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:

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:%.*]]
-;