[IROutliner] Outlining branches with single entry and single exit

[AndrewLitteken]

Summary

Using the similarity found from the IRSimilarity Identifier, we take regions with structural similarity, and deduplicate them into a separate function. The Code Extractor is able to provide most of this functionality.

For simplicity, we start by only outlining regions with a single entry and single exit branch, this reduces the complexity in handling phi nodes outside the region, and handling many sets of outputs for each of the different exit blocks.

[AndrewLitteken]

Updating tests, fixing bugs, and bringing up to date with parent patches.

[paquette]

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

324

just return EnableBranches?

llvm/lib/Transforms/IPO/IROutliner.cpp

36

maybe "DisableBranches" instead?

98

this sentence doesn't really make sense to me?

167

fold this if into the if above?

172

Comments?

191–202

Move this above the if and else, then you can early return from the if portion?

804

this loop could be an any_of?

833

else isn't necessary here

1461

assert that this isn't nullptr?

1515–1521

comments for this bit?

1516

can this be an any_of?

1536

fold this if into the if above?

1621

fold this if into the if above?

1780

assert that this isn't nullptr?

[AndrewLitteken]

llvm/lib/Transforms/IPO/IROutliner.cpp

804

I don't think so? We need to look at all of the successors, and for each one not contained in, it needs to get added to the set. So we need a boolean for each block so I think this makes sense.

[AndrewLitteken]

Updating based on comments

[paquette]

I think this looks fine with nits.

llvm/lib/Transforms/IPO/IROutliner.cpp

36

this could use a comment?

805

drop braces?

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

for (IRInstructionData &ID : *this) {
       BBSet.insert(BB);
     }
   }
 
   /// \param [in,out] BBSet - The set to track the basic blocks.
   /// \param [in,out] BBList - A list in order of use to track the basic blocks.
   /// \returns The BasicBlock the IRSimilarityCandidate ends in.
   void getBasicBlocks(DenseSet<BasicBlock *> &BBSet,
-                      std::vector<BasicBlock *> &BBList) const {
+                      SmallVector<BasicBlock *> &BBList) const {
     for (IRInstructionData &ID : *this) {
       BasicBlock *BB = ID.Inst->getParent();
       if (BBSet.contains(BB))
         continue;
       BBSet.insert(BB);
       BBList.push_back(BB);
     }
   }

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

struct OutlinableRegion {
   DenseMap<unsigned, unsigned> ExtractedArgToAgg;
   DenseMap<unsigned, unsigned> AggArgToExtracted;
 
   /// Marks whether we need to change the order of the arguments when mapping
   /// the old extracted function call to the new aggregate outlined function
   /// call.
   bool ChangedArgOrder = false;
 
+  /// Marks whether this region ends in a branch, there is special handling
+  /// required for the following basic blocks in this case.
+  bool EndsInBranch = false;
+
   /// Mapping of the argument number in the deduplicated function
   /// to a given constant, which is used when creating the arguments to the call
   /// to the newly created deduplicated function.  This is handled separately
   /// since the CodeExtractor does not recognize constants.
   DenseMap<unsigned, Constant *> AggArgToConstant;
 
   /// The global value numbers that are used as outputs for this section. Once
   /// extracted, each output will be stored to an output register.  This
private:
   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> {
     InstructionAllowed() {}
 
-    // TODO: Determine a scheme to resolve when the label is similar enough.
-    bool visitBranchInst(BranchInst &BI) { return false; }
+    bool visitBranchInst(BranchInst &BI) { 
+      return EnableBranches;
+    }
     // TODO: Determine a scheme to resolve when the labels are similar enough.
     bool visitPHINode(PHINode &PN) { return false; }
     // TODO: Handle allocas.
     bool visitAllocaInst(AllocaInst &AI) { return false; }
     // VAArg instructions are not allowed since this could cause difficulty when
     // differentiating between different sets of variable instructions in
     // the deduplicated outlined regions.
     bool visitVAArgInst(VAArgInst &VI) { return false; }
struct InstructionAllowed : public InstVisitor<InstructionAllowed, bool> {
     bool visitFreezeInst(FreezeInst &CI) { return false; }
     // TODO: We do not current handle similarity that changes the control flow.
     bool visitInvokeInst(InvokeInst &II) { return false; }
     // TODO: We do not current handle similarity that changes the control flow.
     bool visitCallBrInst(CallBrInst &CBI) { return false; }
     // TODO: Handle interblock similarity.
     bool visitTerminator(Instruction &I) { return false; }
     bool visitInstruction(Instruction &I) { return true; }
+
+    // The flag variable that marks whether we should allow branch instructions
+    // to be outlined.
+    bool EnableBranches = false;
   };
 
   /// A InstVisitor used to exclude certain instructions from being outlined.
   InstructionAllowed InstructionClassifier;
 };
 
 /// Pass to outline similar regions.
 class IROutlinerPass : public PassInfoMixin<IROutlinerPass> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_IROUTLINER_H

llvm/lib/Transforms/IPO/IROutliner.cpp

 #include <set>
 #include <vector>
 
 #define DEBUG_TYPE "iroutliner"
 
 using namespace llvm;
 using namespace IRSimilarity;
 
+// A command flag to be used for debugging to exclude branches from similarity
+// matching and outlining.
+extern cl::opt<bool> DisableBranches;
+
 // Set to true if the user wants the ir outliner to run on linkonceodr linkage
 // functions. This is false by default because the linker can dedupe linkonceodr
 // functions. Since the outliner is confined to a single module (modulo LTO),
 // this is off by default. It should, however, be the default behavior in
 // LTO.
 static cl::opt<bool> EnableLinkOnceODRIROutlining(
     "enable-linkonceodr-ir-outlining", cl::Hidden,
     cl::desc("Enable the IR outliner on linkonceodr functions"),
struct OutlinableGroup {
   /// 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 branches in the region target a basic block that is outside
+  /// of the region.
+  unsigned BranchesToOutside = 0;
+
   /// 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
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;
+  Instruction *BackInst = Candidate->backInstruction();
+
+  Instruction *EndInst = nullptr;
+  // Check whether the last instruction is a terminator, if it is, we do
+  // not split on the following instruction. We leave the block as it is.  We
+  // also check that this is not the last instruction in the Module, otherwise
+  // the check for whether the current following instruction matches the
+  // previously recorded instruction will be incorrect.
+  if (!BackInst->isTerminator() ||
+      BackInst->getParent() != &BackInst->getFunction()->back()) {
+    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())
+  if (!BackInst->isTerminator() &&
+      EndInst != BackInst->getNextNonDebugInstruction())
     return;
 
   Instruction *StartInst = (*Candidate->begin()).Inst;
   assert(StartInst && "Expected a start instruction?");
   StartBB = StartInst->getParent();
   PrevBB = StartBB;
 
   // The basic block gets split like so:
   // block:                 block:
   //   inst1                  inst1
   //   inst2                  inst2
   //   region1               br block_to_outline
   //   region2              block_to_outline:
   //   region3          ->    region1
   //   region4                region2
   //   inst3                  region3
   //   inst4                  region4
   //                          br block_after_outline
   //                        block_after_outline:
   //                          inst3
   //                          inst4
 
   std::string OriginalName = PrevBB->getName().str();
 
   StartBB = PrevBB->splitBasicBlock(StartInst, OriginalName + "_to_outline");
+  PrevBB->replaceSuccessorsPhiUsesWith(PrevBB, StartBB);
 
-  // This is the case for the inner block since we do not have to include
-  // multiple blocks.
-  EndBB = StartBB;
+  CandidateSplit = true;
+  if (!BackInst->isTerminator()) {
+    EndBB = EndInst->getParent();
     FollowBB = EndBB->splitBasicBlock(EndInst, OriginalName + "_after_outline");
+    EndBB->replaceSuccessorsPhiUsesWith(EndBB, FollowBB);
+    FollowBB->replaceSuccessorsPhiUsesWith(PrevBB, FollowBB);
+    return;
+  }
 
-  CandidateSplit = true;
+  EndBB = BackInst->getParent();
+  EndsInBranch = true;
+  FollowBB = nullptr;
 }
 
 void OutlinableRegion::reattachCandidate() {
   assert(CandidateSplit && "Candidate is not split!");
 
   // The basic block gets reattached like so:
   // block:                        block:
   //   inst1                         inst1
   //   inst2                         inst2
   //   br block_to_outline           region1
   // block_to_outline:        ->     region2
   //   region1                       region3
   //   region2                       region4
   //   region3                       inst3
   //   region4                       inst4
   //   br block_after_outline
   // block_after_outline:
   //   inst3
   //   inst4
   assert(StartBB != nullptr && "StartBB for Candidate is not defined!");
-  assert(FollowBB != nullptr && "StartBB for Candidate is not defined!");
 
   // StartBB should only have one predecessor since we put an unconditional
   // branch at the end of PrevBB when we split the BasicBlock.
   PrevBB = StartBB->getSinglePredecessor();
   assert(PrevBB != nullptr &&
          "No Predecessor for the region start basic block!");
 
   assert(PrevBB->getTerminator() && "Terminator removed from PrevBB!");
-  assert(EndBB->getTerminator() && "Terminator removed from EndBB!");
   PrevBB->getTerminator()->eraseFromParent();
-  EndBB->getTerminator()->eraseFromParent();
 
   moveBBContents(*StartBB, *PrevBB);
 
   BasicBlock *PlacementBB = PrevBB;
   if (StartBB != EndBB)
     PlacementBB = EndBB;
+  if (!EndsInBranch && PlacementBB->getUniqueSuccessor() != nullptr) {
+    assert(FollowBB != nullptr && "FollowBB for Candidate is not defined!");
+    assert(PlacementBB->getTerminator() && "Terminator removed from EndBB!");
+    PlacementBB->getTerminator()->eraseFromParent();
     moveBBContents(*FollowBB, *PlacementBB);
+    PlacementBB->replaceSuccessorsPhiUsesWith(FollowBB, PlacementBB);
+    FollowBB->eraseFromParent();
+  }
 
   PrevBB->replaceSuccessorsPhiUsesWith(StartBB, PrevBB);
-  PrevBB->replaceSuccessorsPhiUsesWith(FollowBB, PlacementBB);
   StartBB->eraseFromParent();
-  FollowBB->eraseFromParent();
 
   // Make sure to save changes back to the StartBB.
   StartBB = PrevBB;
   EndBB = nullptr;
   PrevBB = nullptr;
   FollowBB = nullptr;
 
   CandidateSplit = false;

 
 /// Create a mapping of the output arguments for the \p Region to the output
 /// arguments of the overall outlined function.
 ///
 /// \param [in,out] Region - The region of code to be analyzed.
 /// \param [in] Outputs - The values found by the code extractor.
 static void
 findExtractedOutputToOverallOutputMapping(OutlinableRegion &Region,
-                                          ArrayRef<Value *> Outputs) {
+                                          SetVector<Value *> &Outputs) {
   OutlinableGroup &Group = *Region.Parent;
   IRSimilarityCandidate &C = *Region.Candidate;
 
+  SmallVector<BasicBlock *> BE;
+  DenseSet<BasicBlock *> BBSet;
+  C.getBasicBlocks(BBSet, BE);
+
+  // Find the exits to the region.
+  SmallPtrSet<BasicBlock *, 1> Exits;
+  for (BasicBlock *Block : BE)
+    for (BasicBlock *Succ : successors(Block))
+      if (!BBSet.contains(Succ))
+        Exits.insert(Succ);
+
+  // For now, we check whether we have more than one exit, if we do, we
+  // ignore this region.
+  if (Exits.size() > 1) {
+    Region.IgnoreRegion = true;
+    return;
+  }
+
+  // After determining which blocks exit to PHINodes, we add these PHINodes to
+  // the set of outputs to be processed.  We also check the incoming values of
+  // the PHINodes for whether they should no longer be considered outputs.
+  DenseSet<Value *> PHIWrapped;
+  for (BasicBlock *ExitBB : Exits) {
+    for (PHINode &PN : ExitBB->phis()) {
+      // Find all incoming values from the outlining region.
+      SmallVector<unsigned, 2> IncomingVals;
+      for (unsigned Idx = 0; Idx < PN.getNumIncomingValues(); ++Idx)
+        if (BBSet.contains(PN.getIncomingBlock(Idx)))
+          IncomingVals.push_back(Idx);
+
+      // Do not process PHI if there is one (or fewer) predecessor from region.
+      if (IncomingVals.size() <= 1)
+        continue;
+
+      Region.IgnoreRegion = true;
+      return;
+    }
+  }
+
   // This counts the argument number in the extracted function.
   unsigned OriginalIndex = Region.NumExtractedInputs;
 
   // This counts the argument number in the overall function.
   unsigned TypeIndex = Group.NumAggregateInputs;
   bool TypeFound;
   DenseSet<unsigned> AggArgsUsed;
 
if (Region.IgnoreRegion)
     return;
 
   // Map the inputs found by the CodeExtractor to the arguments found for
   // the overall function.
   findExtractedInputToOverallInputMapping(Region, Inputs, ArgInputs);
 
   // Map the outputs found by the CodeExtractor to the arguments found for
   // the overall function.
-  findExtractedOutputToOverallOutputMapping(Region, Outputs.getArrayRef());
+  findExtractedOutputToOverallOutputMapping(Region, Outputs);
 }
 
 /// Replace the extracted function in the Region with a call to the overall
 /// function constructed from the deduplicated similar regions, replacing and
 /// remapping the values passed to the extracted function as arguments to the
 /// new arguments of the overall function.
 ///
 /// \param [in] M - The module to outline from.
bool IROutliner::isCompatibleWithAlreadyOutlinedCode(
   // 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 =
+  if (!Region.Candidate->backInstruction()->isTerminator()) {
+    Instruction *NewEndInst =
         Region.Candidate->backInstruction()->getNextNonDebugInstruction();
-
-  assert(RealEndInstruction && "Next instruction is a nullptr?");
-  if (Region.Candidate->end()->Inst != RealEndInstruction) {
+    assert(NewEndInst && "Next instruction is a nullptr?");
+    if (Region.Candidate->end()->Inst != NewEndInst) {
       IRInstructionDataList *IDL = Region.Candidate->front()->IDL;
-    Instruction *NewEndInst = RealEndInstruction;
       IRInstructionData *NewEndIRID = new (InstDataAllocator.Allocate())
-        IRInstructionData(*NewEndInst, InstructionClassifier.visit(*NewEndInst),
-                          *IDL);
+          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) {
     if (!nextIRInstructionDataMatchesNextInst(ID))
       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();
   });
 
+  IRSimilarityCandidate &FirstCandidate = CandidateVec[0];
+  // Since outlining a call and a branch instruction will be the same as only
+  // outlinining a call instruction, we ignore it as a space saving.
+  if (FirstCandidate.getLength() == 2) {
+    if (isa<CallInst>(FirstCandidate.front()->Inst) &&
+        isa<BranchInst>(FirstCandidate.back()->Inst))
+        return;
+  }
+
   unsigned CurrentEndIdx = 0;
   for (IRSimilarityCandidate &IRSC : CandidateVec) {
     PreviouslyOutlined = false;
     unsigned StartIdx = IRSC.getStartIdx();
     unsigned EndIdx = IRSC.getEndIdx();
 
     for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
       if (Outlined.contains(Idx)) {
         PreviouslyOutlined = true;
         break;
       }
 
     if (PreviouslyOutlined)
       continue;
 
-    // TODO: If in the future we can outline across BasicBlocks, we will need to
-    // check all BasicBlocks contained in the region.
-    if (IRSC.getStartBB()->hasAddressTaken())
+    // Check over the instructions, and if the basic block has its address
+    // taken for use somewhere else, we do not outline that block.
+    bool BBHasAddressTaken = any_of(IRSC, [](IRInstructionData &ID){
+      return ID.Inst->getParent()->hasAddressTaken();
+    });
+
+    if (BBHasAddressTaken)
       continue;
 
     if (IRSC.front()->Inst->getFunction()->hasLinkOnceODRLinkage() &&
         !OutlineFromLinkODRs)
       continue;
 
     // Greedily prune out any regions that will overlap with already chosen
     // regions.
     if (CurrentEndIdx != 0 && StartIdx <= CurrentEndIdx)
       continue;
 
     bool BadInst = any_of(IRSC, [this](IRInstructionData &ID) {
       if (!nextIRInstructionDataMatchesNextInst(ID))
         return true;
 
       return !this->InstructionClassifier.visit(ID.Inst);
     });
 
     if (BadInst)
       continue;
 
     OutlinableRegion *OS = new (RegionAllocator.Allocate())
         OutlinableRegion(IRSC, CurrentGroup);

 /// \param [in] CurrentGroup - The collection of OutlinableRegions to analyze.
 /// \param [in] TTI - The TargetTransformInfo used to collect information for
 /// new instruction costs.
 /// \returns the additional cost to handle the outputs.
 static InstructionCost findCostForOutputBlocks(Module &M,
                                                OutlinableGroup &CurrentGroup,
                                                TargetTransformInfo &TTI) {
   InstructionCost OutputCost = 0;
+  unsigned NumOutputBranches = 0;
+
+  IRSimilarityCandidate &Candidate = *CurrentGroup.Regions[0]->Candidate;
+  DenseSet<BasicBlock *> CandidateBlocks;
+  Candidate.getBasicBlocks(CandidateBlocks);
+
+  // Count the number of different output branches that point to blocks outside
+  // of the region.
+  DenseSet<BasicBlock *> FoundBlocks;
+  for (IRInstructionData &ID : Candidate) {
+    if (!isa<BranchInst>(ID.Inst))
+      continue;
+
+    for (Value *V : ID.OperVals) {
+      BasicBlock *BB = static_cast<BasicBlock *>(V);
+      DenseSet<BasicBlock *>::iterator CBIt = CandidateBlocks.find(BB);
+      if (CBIt != CandidateBlocks.end() || FoundBlocks.contains(BB))
+        continue;
+      FoundBlocks.insert(BB);
+      NumOutputBranches++;
+    }
+  }
+
+  CurrentGroup.BranchesToOutside = NumOutputBranches;
 
   for (const ArrayRef<unsigned> &OutputUse :
        CurrentGroup.OutputGVNCombinations) {
-    IRSimilarityCandidate &Candidate = *CurrentGroup.Regions[0]->Candidate;
     for (unsigned GVN : OutputUse) {
       Optional<Value *> OV = Candidate.fromGVN(GVN);
       assert(OV.hasValue() && "Could not find value for GVN?");
       Value *V = OV.getValue();
       InstructionCost StoreCost =
           TTI.getMemoryOpCost(Instruction::Load, V->getType(), Align(1), 0,
                               TargetTransformInfo::TCK_CodeSize);
 
       // An instruction cost is added for each store set that needs to occur for
       // various output combinations inside the function, plus a branch to
       // return to the exit block.
       LLVM_DEBUG(dbgs() << "Adding: " << StoreCost
                         << " instructions to cost for output of type "
                         << *V->getType() << "\n");
-      OutputCost += StoreCost;
+      OutputCost += StoreCost * NumOutputBranches;
     }
 
     InstructionCost BranchCost =
         TTI.getCFInstrCost(Instruction::Br, TargetTransformInfo::TCK_CodeSize);
     LLVM_DEBUG(dbgs() << "Adding " << BranchCost << " to the current cost for"
                       << " a branch instruction\n");
-    OutputCost += BranchCost;
+    OutputCost += BranchCost * NumOutputBranches;
   }
 
   // If there is more than one output scheme, we must have a comparison and
   // branch for each different item in the switch statement.
   if (CurrentGroup.OutputGVNCombinations.size() > 1) {
     InstructionCost ComparisonCost = TTI.getCmpSelInstrCost(
         Instruction::ICmp, Type::getInt32Ty(M.getContext()),
         Type::getInt32Ty(M.getContext()), CmpInst::BAD_ICMP_PREDICATE,
         TargetTransformInfo::TCK_CodeSize);
     InstructionCost BranchCost =
         TTI.getCFInstrCost(Instruction::Br, TargetTransformInfo::TCK_CodeSize);
 
     unsigned DifferentBlocks = CurrentGroup.OutputGVNCombinations.size();
     InstructionCost TotalCost = ComparisonCost * BranchCost * DifferentBlocks;
 
     LLVM_DEBUG(dbgs() << "Adding: " << TotalCost
                       << " instructions for each switch case for each different"
                       << " output path in a function\n");
-    OutputCost += TotalCost;
+    OutputCost += TotalCost * NumOutputBranches;
   }
 
   return OutputCost;
 }
 
 void IROutliner::findCostBenefit(Module &M, OutlinableGroup &CurrentGroup) {
   InstructionCost RegionBenefit = findBenefitFromAllRegions(CurrentGroup);
   CurrentGroup.Benefit += RegionBenefit;
if (OutputMappings.find(Outputs[OutputIdx.getValue()]) ==
     LLVM_DEBUG(dbgs() << "Mapping extracted output " << *Orig << " to "
                       << *Outputs[OutputIdx.getValue()] << "\n");
     OutputMappings.insert(std::make_pair(LI, Orig));
   }
 }
 
 bool IROutliner::extractSection(OutlinableRegion &Region) {
   SetVector<Value *> ArgInputs, Outputs, SinkCands;
-  Region.CE->findInputsOutputs(ArgInputs, Outputs, SinkCands);
-
   assert(Region.StartBB && "StartBB for the OutlinableRegion is nullptr!");
-  assert(Region.FollowBB && "FollowBB for the OutlinableRegion is nullptr!");
+  BasicBlock *InitialStart = Region.StartBB;
   Function *OrigF = Region.StartBB->getParent();
   CodeExtractorAnalysisCache CEAC(*OrigF);
-  Region.ExtractedFunction = Region.CE->extractCodeRegion(CEAC);
+  Region.ExtractedFunction =
+      Region.CE->extractCodeRegion(CEAC, ArgInputs, Outputs);
 
   // If the extraction was successful, find the BasicBlock, and reassign the
   // OutlinableRegion blocks
   if (!Region.ExtractedFunction) {
     LLVM_DEBUG(dbgs() << "CodeExtractor failed to outline " << Region.StartBB
                       << "\n");
     Region.reattachCandidate();
     return false;
   }
 
-  BasicBlock *RewrittenBB = Region.FollowBB->getSinglePredecessor();
+  // Get the block containing the called branch, and reassign the blocks as
+  // necessary.  If the original block still exists, it is because we ended on
+  // a branch instruction, and so we move the contents into the block before
+  // and assign the previous block correctly.
+  User *InstAsUser = Region.ExtractedFunction->user_back();
+  BasicBlock *RewrittenBB = cast<Instruction>(InstAsUser)->getParent();
+  Region.PrevBB = RewrittenBB->getSinglePredecessor();
+  assert(Region.PrevBB && "PrevBB is nullptr?");
+  if (Region.PrevBB == InitialStart) {
+    BasicBlock *NewPrev = InitialStart->getSinglePredecessor();
+    Instruction *BI = NewPrev->getTerminator();
+    BI->eraseFromParent();
+    moveBBContents(*InitialStart, *NewPrev);
+    Region.PrevBB = NewPrev;
+    InitialStart->eraseFromParent();
+  }
+
   Region.StartBB = RewrittenBB;
   Region.EndBB = RewrittenBB;
 
   // The sequences of outlinable regions has now changed.  We must fix the
   // IRInstructionDataList for consistency.  Although they may not be illegal
   // instructions, they should not be compared with anything else as they
   // should not be outlined in this round.  So marking these as illegal is
   // allowed.
for (Instruction &I : *RewrittenBB)
     } else if (LoadInst *LI = dyn_cast<LoadInst>(&I))
       updateOutputMapping(Region, Outputs.getArrayRef(), LI);
   Region.reattachCandidate();
   return true;
 }
 
 unsigned IROutliner::doOutline(Module &M) {
   // Find the possible similarity sections.
+  InstructionClassifier.EnableBranches = !DisableBranches;
   IRSimilarityIdentifier &Identifier = getIRSI(M);
   SimilarityGroupList &SimilarityCandidates = *Identifier.getSimilarity();
 
   // Sort them by size of extracted sections
   unsigned OutlinedFunctionNum = 0;
   // If we only have one SimilarityGroup in SimilarityCandidates, we do not have
   // to sort them by the potential number of instructions to be outlined
   if (SimilarityCandidates.size() > 1)
for (OutlinableRegion *OS : CurrentGroup.Regions) {
       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};
+      SmallVector<BasicBlock *> BE;
+      DenseSet<BasicBlock *> BBSet;
+      OS->Candidate->getBasicBlocks(BBSet, BE);
       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);
 
       // We recombine the blocks together now that we have gathered all the
for (OutlinableGroup *CG : NegativeCostGroups) {
     }
 
     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};
+      SmallVector<BasicBlock *> BE;
+      DenseSet<BasicBlock *> BBSet;
+      OS->Candidate->getBasicBlocks(BBSet, BE);
       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++)

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 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: 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 4 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:  <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>
+; 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:          ' regions due to estimated increase of '
-; YAML-NEXT:   - InstructionIncrease: '13'
+; 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: '6'
+; 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:        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: '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:        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:   - 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: '2'
+; 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: '12'
+; 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:        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: '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: '3'
+; 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: '4'
+; 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: '14'
+; 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: '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: '15'
+; 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: '6'
+; 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: '11'
+; 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:        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:   - 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: '7'
+; 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: '8'
+; 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: '18'
+; YAML-NEXT:   - InstructionIncrease: '17'
 ; 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:   - 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: '9'
+; 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:         '1'
+; 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:

llvm/test/Transforms/IROutliner/outlining-across-branch.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --include-generated-funcs
+; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
+
+; This checks that we are able to outline exactly the same branch structure
+; while also outlining similar items on either side of the branch.
+
+define void @outline_outputs1() #0 {
+entry:
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %output = alloca i32, align 4
+  %result = alloca i32, align 4
+  %output2 = alloca i32, align 4
+  %result2 = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  store i32 3, i32* %b, align 4
+  br label %next
+next:
+  store i32 2, i32* %output, align 4
+  store i32 3, i32* %result, align 4
+  ret void
+}
+
+define void @outline_outputs2() #0 {
+entry:
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %output = alloca i32, align 4
+  %result = alloca i32, align 4
+  %output2 = alloca i32, align 4
+  %result2 = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  store i32 3, i32* %b, align 4
+  br label %next
+next:
+  store i32 2, i32* %output, align 4
+  store i32 3, i32* %result, align 4
+  ret void
+}
+; CHECK-LABEL: @outline_outputs1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[OUTPUT:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[RESULT:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[OUTPUT2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[RESULT2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    call void @outlined_ir_func_0(i32* [[A]], i32* [[B]], i32* [[OUTPUT]], i32* [[RESULT]])
+; CHECK-NEXT:    ret void
+;
+;
+; CHECK-LABEL: @outline_outputs2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[OUTPUT:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[RESULT:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[OUTPUT2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[RESULT2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    call void @outlined_ir_func_0(i32* [[A]], i32* [[B]], i32* [[OUTPUT]], i32* [[RESULT]])
+; CHECK-NEXT:    ret void
+;
+;
+; CHECK: define internal void @outlined_ir_func_0(
+; CHECK:  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:    br label [[NEXT:%.*]]
+; CHECK:       next:
+; CHECK-NEXT:    store i32 2, i32* [[TMP2:%.*]], align 4
+; CHECK-NEXT:    store i32 3, i32* [[TMP3:%.*]], align 4
+; CHECK-NEXT:    br label [[ENTRY_AFTER_OUTLINE_EXITSTUB:%.*]]
+; CHECK:       entry_after_outline.exitStub:
+; CHECK-NEXT:    ret void
+;

llvm/test/Transforms/IROutliner/outlining-basic-branches.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --include-generated-funcs
+; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
+
+; This checks that we are able to outline exactly the same structure without
+; any other items to outline.
+
+define void @outline_outputs1() #0 {
+entry:
+  br label %next
+next:
+  br label %next2
+next2:
+  br label %next
+next3:
+  %a = alloca i32, align 4
+  br label %next4
+next4:
+  br label %next3
+next5:
+  br label %next6
+next6:
+  %b = alloca i32, align 4
+  ret void
+}
+
+; CHECK-LABEL: @outline_outputs1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[NEXT:%.*]]
+; CHECK:       next:
+; CHECK-NEXT:    call void @outlined_ir_func_0()
+; CHECK-NEXT:    br label [[NEXT]]
+; CHECK:       next3:
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    call void @outlined_ir_func_0()
+; CHECK-NEXT:    br label [[NEXT3:%.*]]
+; CHECK:       next5:
+; CHECK-NEXT:    br label [[NEXT6:%.*]]
+; CHECK:       next6:
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    ret void
+;
+;
+; CHECK: define internal void @outlined_ir_func_0(
+; CHECK:  newFuncRoot:
+; CHECK-NEXT:    br label [[NEXT_TO_OUTLINE:%.*]]
+; CHECK:       next_to_outline:
+; CHECK-NEXT:    br label [[NEXT2:%.*]]
+; CHECK:       next2:
+; CHECK-NEXT:    br label [[NEXT_EXITSTUB:%.*]]
+; CHECK:       next.exitStub:
+; CHECK-NEXT:    ret void
+;

llvm/test/Transforms/IROutliner/outlining-multiple-exits.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --include-generated-funcs
+; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
+
+; Here we have multiple exits, but we can't actually outline anything but
+; single entry and single exits yet, we check to make sure it doesn't happen.
+
+define void @outline_outputs1() #0 {
+entry:
+  %output = alloca i32, align 4
+  %result = alloca i32, align 4
+  %output2 = alloca i32, align 4
+  %result2 = alloca i32, align 4
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  br label %block_2
+block_1:
+  %a2 = alloca i32, align 4
+  %b2 = alloca i32, align 4
+  br label %block_2
+block_2:
+  %a2val = load i32, i32* %a
+  %b2val = load i32, i32* %b
+  %add2 = add i32 2, %a2val
+  %mul2 = mul i32 2, %b2val
+  br label %block_5
+block_3:
+  %aval = load i32, i32* %a
+  %bval = load i32, i32* %b
+  %add = add i32 2, %aval
+  %mul = mul i32 2, %bval
+  br label %block_4
+block_4:
+  store i32 %add, i32* %output, align 4
+  store i32 %mul, i32* %result, align 4
+  br label %block_6
+block_5:
+  store i32 %add2, i32* %output, align 4
+  store i32 %mul2, i32* %result, align 4
+  br label %block_7
+block_6:
+  %div = udiv i32 %aval, %bval
+  ret void
+block_7:
+  %sub = sub i32 %a2val, %b2val
+  ret void
+}
+
+define void @outline_outputs2() #0 {
+entry:
+  %output = alloca i32, align 4
+  %result = alloca i32, align 4
+  %output2 = alloca i32, align 4
+  %result2 = alloca i32, align 4
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  br label %block_2
+block_1:
+  %a2 = alloca i32, align 4
+  %b2 = alloca i32, align 4
+  br label %block_2
+block_2:
+  %a2val = load i32, i32* %a
+  %b2val = load i32, i32* %b
+  %add2 = add i32 2, %a2val
+  %mul2 = mul i32 2, %b2val
+  br label %block_5
+block_3:
+  %aval = load i32, i32* %a
+  %bval = load i32, i32* %b
+  %add = add i32 2, %aval
+  %mul = mul i32 2, %bval
+  br label %block_4
+block_4:
+  store i32 %add, i32* %output, align 4
+  store i32 %mul, i32* %result, align 4
+  br label %block_7
+block_5:
+  store i32 %add2, i32* %output, align 4
+  store i32 %mul2, i32* %result, align 4
+  br label %block_6
+block_6:
+  %diff = sub i32 %a2val, %b2val
+  ret void
+block_7:
+  %quot = udiv i32 %aval, %bval
+  ret void
+}
+; CHECK-LABEL: @outline_outputs1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[OUTPUT:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[RESULT:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[OUTPUT2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[RESULT2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    br label [[BLOCK_2:%.*]]
+; CHECK:       block_1:
+; CHECK-NEXT:    [[A2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    br label [[BLOCK_2]]
+; CHECK:       block_2:
+; CHECK-NEXT:    [[A2VAL:%.*]] = load i32, i32* [[A]], align 4
+; CHECK-NEXT:    [[B2VAL:%.*]] = load i32, i32* [[B]], align 4
+; CHECK-NEXT:    [[ADD2:%.*]] = add i32 2, [[A2VAL]]
+; CHECK-NEXT:    [[MUL2:%.*]] = mul i32 2, [[B2VAL]]
+; CHECK-NEXT:    br label [[BLOCK_5:%.*]]
+; CHECK:       block_3:
+; CHECK-NEXT:    [[AVAL:%.*]] = load i32, i32* [[A]], align 4
+; CHECK-NEXT:    [[BVAL:%.*]] = load i32, i32* [[B]], align 4
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 2, [[AVAL]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 2, [[BVAL]]
+; CHECK-NEXT:    br label [[BLOCK_4:%.*]]
+; CHECK:       block_4:
+; CHECK-NEXT:    store i32 [[ADD]], i32* [[OUTPUT]], align 4
+; CHECK-NEXT:    store i32 [[MUL]], i32* [[RESULT]], align 4
+; CHECK-NEXT:    br label [[BLOCK_6:%.*]]
+; CHECK:       block_5:
+; CHECK-NEXT:    call void @outlined_ir_func_0(i32 [[ADD2]], i32* [[OUTPUT]], i32 [[MUL2]], i32* [[RESULT]])
+; CHECK-NEXT:    br label [[BLOCK_7:%.*]]
+; CHECK:       block_6:
+; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[AVAL]], [[BVAL]]
+; CHECK-NEXT:    ret void
+; CHECK:       block_7:
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[A2VAL]], [[B2VAL]]
+; CHECK-NEXT:    ret void
+;
+;
+; CHECK-LABEL: @outline_outputs2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[OUTPUT:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[RESULT:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[OUTPUT2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[RESULT2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    br label [[BLOCK_2:%.*]]
+; CHECK:       block_1:
+; CHECK-NEXT:    [[A2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B2:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    br label [[BLOCK_2]]
+; CHECK:       block_2:
+; CHECK-NEXT:    [[A2VAL:%.*]] = load i32, i32* [[A]], align 4
+; CHECK-NEXT:    [[B2VAL:%.*]] = load i32, i32* [[B]], align 4
+; CHECK-NEXT:    [[ADD2:%.*]] = add i32 2, [[A2VAL]]
+; CHECK-NEXT:    [[MUL2:%.*]] = mul i32 2, [[B2VAL]]
+; CHECK-NEXT:    br label [[BLOCK_5:%.*]]
+; CHECK:       block_3:
+; CHECK-NEXT:    [[AVAL:%.*]] = load i32, i32* [[A]], align 4
+; CHECK-NEXT:    [[BVAL:%.*]] = load i32, i32* [[B]], align 4
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 2, [[AVAL]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 2, [[BVAL]]
+; CHECK-NEXT:    br label [[BLOCK_4:%.*]]
+; CHECK:       block_4:
+; CHECK-NEXT:    store i32 [[ADD]], i32* [[OUTPUT]], align 4
+; CHECK-NEXT:    store i32 [[MUL]], i32* [[RESULT]], align 4
+; CHECK-NEXT:    br label [[BLOCK_7:%.*]]
+; CHECK:       block_5:
+; CHECK-NEXT:    call void @outlined_ir_func_0(i32 [[ADD2]], i32* [[OUTPUT]], i32 [[MUL2]], i32* [[RESULT]])
+; CHECK-NEXT:    br label [[BLOCK_6:%.*]]
+; CHECK:       block_6:
+; CHECK-NEXT:    [[DIFF:%.*]] = sub i32 [[A2VAL]], [[B2VAL]]
+; CHECK-NEXT:    ret void
+; CHECK:       block_7:
+; CHECK-NEXT:    [[QUOT:%.*]] = udiv i32 [[AVAL]], [[BVAL]]
+; CHECK-NEXT:    ret void
+;
+;
+; CHECK: define internal void @outlined_ir_func_0(
+; CHECK-NEXT:  newFuncRoot:
+; CHECK-NEXT:    br label [[BLOCK_5_TO_OUTLINE:%.*]]
+; CHECK:       block_5_to_outline:
+; CHECK-NEXT:    store i32 [[TMP0:%.*]], i32* [[TMP1:%.*]], align 4
+; CHECK-NEXT:    store i32 [[TMP2:%.*]], i32* [[TMP3:%.*]], align 4
+; CHECK-NEXT:    br label [[BLOCK_7_EXITSTUB:%.*]]
+; CHECK:       block_7.exitStub:
+; CHECK-NEXT:    ret void
+;

llvm/test/Transforms/IROutliner/region-end-of-module.ll

 for.body:
   %inc = add nsw i32 2, 1
   br label %for.cond1
 
 for.end:
   %inc3 = add nsw i32 2, 1
   br label %for.cond1
 }
-; CHECK-LABEL: @foo(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
-; CHECK:       for.cond1:
-; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
-; CHECK:       for.body:
-; CHECK-NEXT:    [[INC:%.*]] = add nsw i32 2, 1
-; CHECK-NEXT:    br label [[FOR_COND1]]
-; CHECK:       for.end:
-; CHECK-NEXT:    [[INC3:%.*]] = add nsw i32 2, 1
-; CHECK-NEXT:    br label [[FOR_COND1]]
-;
 
 ; These are for testing if return instructions or unreachable instructions are
 ; matched for similarity.
 define void @foo1() {
 entry:
   br label %for.cond1
 
 for.cond1:

 for.body:
   %inc = add nsw i32 2, 1
   unreachable
 
 for.end:
   %inc3 = add nsw i32 2, 1
   unreachable
 }
+
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
+; CHECK:       for.cond1:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    call void @outlined_ir_func_1()
+; CHECK-NEXT:    br label [[FOR_COND1]]
+; CHECK:       for.end:
+; CHECK-NEXT:    call void @outlined_ir_func_1()
+; CHECK-NEXT:    br label [[FOR_COND1]]
+;
+;
+; CHECK-LABEL: @foo1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @outlined_ir_func_0()
+; CHECK-NEXT:    ret void
+; CHECK:       for.end:
+; CHECK-NEXT:    [[INC3:%.*]] = add nsw i32 2, 1
+; CHECK-NEXT:    ret void
+;
+;
+; CHECK-LABEL: @foo2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @outlined_ir_func_0()
+; CHECK-NEXT:    unreachable
+; CHECK:       for.end:
+; CHECK-NEXT:    [[INC3:%.*]] = add nsw i32 2, 1
+; CHECK-NEXT:    unreachable
+;
+;
+; CHECK: define internal void @outlined_ir_func_0(
+; CHECK-NEXT:  newFuncRoot:
+; CHECK-NEXT:    br label [[ENTRY_TO_OUTLINE:%.*]]
+; CHECK:       entry_to_outline:
+; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
+; CHECK:       for.cond1:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INC:%.*]] = add nsw i32 2, 1
+; CHECK-NEXT:    br label [[ENTRY_AFTER_OUTLINE_EXITSTUB:%.*]]
+; CHECK:       entry_after_outline.exitStub:
+; CHECK-NEXT:    ret void
+;
+;
+; CHECK: define internal void @outlined_ir_func_1(
+; CHECK-NEXT:  newFuncRoot:
+; CHECK-NEXT:    br label [[FOR_BODY_TO_OUTLINE:%.*]]
+; CHECK:       for.body_to_outline:
+; CHECK-NEXT:    [[INC:%.*]] = add nsw i32 2, 1
+; CHECK-NEXT:    br label [[FOR_COND1_EXITSTUB:%.*]]
+; CHECK:       for.cond1.exitStub:
+; CHECK-NEXT:    ret void
+;