[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?

308

why?

llvm/lib/Transforms/IPO/IROutliner.cpp

136

Unnecessary whitespace change?

1351

clang format braces

1359

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

1383

Probably don't need the variable here?

Just

return any_of(...);

1723

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

276–277

is it actually necessary to use this here?

277

Is ID a pointer? Can you loop over it like

for (IRInstructionData *ID ... )

to make that clear?

278

Why is this variable necessary?

1350

Comment?

1354

Comment?

1354

What happens if this is nullptr?

1368

none_of?

1379

Do you need this here?

also you can probably just write

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

1715

Would this be better as a SmallVector?

1723

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

1764–1767

This could use a comment?

1814

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

1825

Comment?

1866

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

[AndrewLitteken]

llvm/lib/Transforms/IPO/IROutliner.cpp

1354

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.

1379

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

1379

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. OutlinableRegions are incomptaible when there are overlapping
+  /// instructions, or code that has not been recorded has been 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 isCompatibleWithAlreadyOutlinedCode(const 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
private:
 
   /// 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) {
-    switch (I.getOpcode()) {
+  for (IRInstructionData &ID : *Candidate) {
+    Instruction *I = ID.Inst;
+    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:
-      Benefit += TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);
+      Benefit += TTI.getInstructionCost(I, TargetTransformInfo::TCK_CodeSize);
       break;
     }
   }
 
   return Benefit;
 }
 
 /// Find whether \p Region matches the global value numbering to Constant
void IROutliner::deduplicateExtractedSections(
   }
 
   // Create a switch statement to handle the different output schemes.
   createSwitchStatement(M, CurrentGroup, CurrentGroup.EndBB, OutputStoreBBs);
 
   OutlinedFunctionNum++;
 }
 
+bool IROutliner::isCompatibleWithAlreadyOutlinedCode(
+    const OutlinableRegion &Region) {
+  IRSimilarityCandidate *IRSC = Region.Candidate;
+  unsigned StartIdx = IRSC->getStartIdx();
+  unsigned EndIdx = IRSC->getEndIdx();
+
+  // A check to make sure that we are not about to attempt to outline something
+  // that has already been outlined.
+  for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
+    if (Outlined.contains(Idx))
+      return false;
+
+  // We check if the recorded instruction matches the actual next instruction,
+  // if it does not, we fix it in the InstructionDataList.
+  Instruction *RealEndInstruction =
+      Region.Candidate->backInstruction()->getNextNonDebugInstruction();
+
+  assert(RealEndInstruction && "Next instruction is a nullptr?");
+  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 none_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 !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) {
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);
 
     // 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)
       continue;
 
     // Determine if there are any values that are the same constant throughout
     // each section in the set.
     NotSame.clear();
     CurrentGroup.findSameConstants(NotSame);
 
     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;
+    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 to the region. This makes the region no longer viable
       // to be split, so we ignore it for outlining.
       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();
+
+      // We recombine the blocks together now that we have gathered all the
+      // needed information.
     }
 
     CurrentGroup.Regions = std::move(OutlinedRegions);
 
     if (CurrentGroup.Regions.empty())
       continue;
 
     CurrentGroup.collectGVNStoreSets(M);
 
     if (CostModel)
       findCostBenefit(M, CurrentGroup);
 
-    // If we are adhering to the cost model, reattach all the candidates
+    // If we are adhering to the cost model, skip those groups where the cost
+    // outweighs the benefits.
     if (CurrentGroup.Cost >= CurrentGroup.Benefit && CostModel) {
-      for (OutlinableRegion *OS : CurrentGroup.Regions)
-        OS->reattachCandidate();
-      OptimizationRemarkEmitter &ORE = getORE(
-          *CurrentGroup.Regions[0]->Candidate->getFunction());
+      OptimizationRemarkEmitter &ORE =
+          getORE(*CurrentGroup.Regions[0]->Candidate->getFunction());
       ORE.emit([&]() {
         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()))
           << " regions due to estimated increase of "
           << ore::NV("InstructionIncrease",
                      CurrentGroup.Cost - CurrentGroup.Benefit)
           << " instructions at locations ";
         interleave(
             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)
+    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) {
+      // We check whether our region is compatible with what has already been
+      // outlined, and whether we need to ignore this item.
+      if (!isCompatibleWithAlreadyOutlinedCode(*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) {
+      SmallVector<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/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_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:%.*]]
-;
+; CHECK:       entry_after_outline.exitStub:
+; CHECK-NEXT:    ret void