[MachineOutliner] NFC - Move intermediate data structures to MachineOutliner.h

[paquette]

Summary

This is setting up to fix bug 37573 cleanly. Although this is NFC, it involves introducing a header file for some outliner data structures. If possible, I'd like a bit of input on how I've set up the header file etc. Other than that, the changes are

• Renaming things to fit the new header file
• Removing the vector of std::pairs that was used to communicate candidate information between the target and the outliner.

This moves data structures that are technically both used in some way by the target and the general-purpose outlining algorithm into MachineOutliner.h. In particular, the Candidate class is of importance.

Before, the outliner passed the locations of Candidates to the target, which would then make some decisions about the prospective outlined function. This change allows us to just pass Candidates along to the target. This will allow the target to discard Candidates that would be considered unsafe before cost calculation. Thus, we will be able to remove the unsafe candidates described in the bug without resorting to torching the entire prospective function.

Also, as a side-effect, it makes the outliner a bit cleaner.

https://bugs.llvm.org/show_bug.cgi?id=37573

[efriedma]

Please post diffs to Phabricator with full context.

Please commit the whitespace-only changes separately.

include/llvm/CodeGen/MachineOutliner.h

195

Newline?

lib/CodeGen/MachineOutliner.cpp

1217

Is this change related somehow? It's not obvious.

[paquette]

Got rid of the whitespace changes and remembered to pass -U999999 this time.

(Could probably also move renaming MInfo to TCI to a separate patch if that'd be less annoying. :))

[paquette]

lib/CodeGen/MachineOutliner.cpp

1217

That was from some early experimentation with the patch and accidentally made it in... Removed it.

[efriedma]

LGTM

[paquette]

Closed in r333952 (https://reviews.llvm.org/rL333952)

include/llvm/CodeGen/MachineOutliner.h

+//===---- MachineOutliner.h - Outliner data structures ------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// Contains all data structures shared between the outliner implemented in
+/// MachineOutliner.cpp and target implementations of the outliner.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_MACHINEOUTLINER_H
+#define LLVM_MACHINEOUTLINER_H
+
+#include "llvm/CodeGen/MachineFunction.h"
+
+namespace outliner {
+
+using namespace llvm;
+
+/// Represents how an instruction should be mapped by the outliner.
+/// \p Legal instructions are those which are safe to outline.
+/// \p LegalTerminator instructions are safe to outline, but only as the
+/// last instruction in a sequence.
+/// \p Illegal instructions are those which cannot be outlined.
+/// \p Invisible instructions are instructions which can be outlined, but
+/// shouldn't actually impact the outlining result.
+enum InstrType { Legal, LegalTerminator, Illegal, Invisible };
+
+/// Describes the number of instructions that it will take to call and
+/// construct a frame for a given outlining candidate.
+struct TargetCostInfo {
+  /// Represents the size of a sequence in bytes. (Some instructions vary
+  /// widely in size, so just counting the instructions isn't very useful.)
+  unsigned SequenceSize;
+
+  /// Number of instructions to call an outlined function for this candidate.
+  unsigned CallOverhead;
+
+  /// Number of instructions to construct an outlined function frame
+  /// for this candidate.
+  unsigned FrameOverhead;
+
+  /// Represents the specific instructions that must be emitted to
+  /// construct a call to this candidate.
+  unsigned CallConstructionID;
+
+  /// Represents the specific instructions that must be emitted to
+  /// construct a frame for this candidate's outlined function.
+  unsigned FrameConstructionID;
+
+  TargetCostInfo() {}
+  TargetCostInfo(unsigned SequenceSize, unsigned CallOverhead,
+                 unsigned FrameOverhead, unsigned CallConstructionID,
+                 unsigned FrameConstructionID)
+      : SequenceSize(SequenceSize), CallOverhead(CallOverhead),
+        FrameOverhead(FrameOverhead), CallConstructionID(CallConstructionID),
+        FrameConstructionID(FrameConstructionID) {}
+};
+
+/// An individual sequence of instructions to be replaced with a call to
+/// an outlined function.
+struct Candidate {
+private:
+  /// The start index of this \p Candidate in the instruction list.
+  unsigned StartIdx;
+
+  /// The number of instructions in this \p Candidate.
+  unsigned Len;
+
+  // The first instruction in this \p Candidate.
+  MachineBasicBlock::iterator FirstInst;
+
+  // The last instruction in this \p Candidate.
+  MachineBasicBlock::iterator LastInst;
+
+  // The basic block that contains this Candidate.
+  MachineBasicBlock *MBB;
+
+public:
+  /// The index of this \p Candidate's \p OutlinedFunction in the list of
+  /// \p OutlinedFunctions.
+  unsigned FunctionIdx;
+
+  /// Set to false if the candidate overlapped with another candidate.
+  bool InCandidateList = true;
+
+  /// Contains all target-specific information for this \p Candidate.
+  TargetCostInfo TCI;
+
+  /// Return the number of instructions in this Candidate.
+  unsigned getLength() const { return Len; }
+
+  /// Return the start index of this candidate.
+  unsigned getStartIdx() const { return StartIdx; }
+
+  /// Return the end index of this candidate.
+  unsigned getEndIdx() const { return StartIdx + Len - 1; }
+
+  MachineBasicBlock::iterator &front() { return FirstInst; }
+  MachineBasicBlock::iterator &back() { return LastInst; }
+  MachineFunction *getMF() const { return MBB->getParent(); }
+  MachineBasicBlock *getMBB() const { return MBB; }
+
+  /// The number of instructions that would be saved by outlining every
+  /// candidate of this type.
+  ///
+  /// This is a fixed value which is not updated during the candidate pruning
+  /// process. It is only used for deciding which candidate to keep if two
+  /// candidates overlap. The true benefit is stored in the OutlinedFunction
+  /// for some given candidate.
+  unsigned Benefit = 0;
+
+  Candidate(unsigned StartIdx, unsigned Len,
+            MachineBasicBlock::iterator &FirstInst,
+            MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB,
+            unsigned FunctionIdx)
+      : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
+        MBB(MBB), FunctionIdx(FunctionIdx) {}
+
+  /// Used to ensure that \p Candidates are outlined in an order that
+  /// preserves the start and end indices of other \p Candidates.
+  bool operator<(const Candidate &RHS) const {
+    return getStartIdx() > RHS.getStartIdx();
+  }
+};
+
+/// The information necessary to create an outlined function for some
+/// class of candidate.
+struct OutlinedFunction {
+
+private:
+  /// The number of candidates for this \p OutlinedFunction.
+  unsigned OccurrenceCount = 0;
+
+public:
+  std::vector<std::shared_ptr<Candidate>> Candidates;
+
+  /// The actual outlined function created.
+  /// This is initialized after we go through and create the actual function.
+  MachineFunction *MF = nullptr;
+
+  /// A number assigned to this function which appears at the end of its name.
+  unsigned Name;
+
+  /// The sequence of integers corresponding to the instructions in this
+  /// function.
+  std::vector<unsigned> Sequence;
+
+  /// Contains all target-specific information for this \p OutlinedFunction.
+  TargetCostInfo TCI;
+
+  /// Return the number of candidates for this \p OutlinedFunction.
+  unsigned getOccurrenceCount() { return OccurrenceCount; }
+
+  /// Decrement the occurrence count of this OutlinedFunction and return the
+  /// new count.
+  unsigned decrement() {
+    assert(OccurrenceCount > 0 && "Can't decrement an empty function!");
+    OccurrenceCount--;
+    return getOccurrenceCount();
+  }
+
+  /// Return the number of bytes it would take to outline this
+  /// function.
+  unsigned getOutliningCost() {
+    return (OccurrenceCount * TCI.CallOverhead) + TCI.SequenceSize +
+           TCI.FrameOverhead;
+  }
+
+  /// Return the size in bytes of the unoutlined sequences.
+  unsigned getNotOutlinedCost() { return OccurrenceCount * TCI.SequenceSize; }
+
+  /// Return the number of instructions that would be saved by outlining
+  /// this function.
+  unsigned getBenefit() {
+    unsigned NotOutlinedCost = getNotOutlinedCost();
+    unsigned OutlinedCost = getOutliningCost();
+    return (NotOutlinedCost < OutlinedCost) ? 0
+                                            : NotOutlinedCost - OutlinedCost;
+  }
+
+  OutlinedFunction(unsigned Name, unsigned OccurrenceCount,
+                   const std::vector<unsigned> &Sequence, TargetCostInfo &TCI)
+      : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence),
+        TCI(TCI) {}
+};
+} // namespace outliner
+
+#endif
 No newline at end of file

include/llvm/CodeGen/TargetInstrInfo.h

 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
+#include "llvm/CodeGen/MachineOutliner.h"
 #include "llvm/CodeGen/PseudoSourceValue.h"
 #include "llvm/MC/MCInstrInfo.h"
 #include "llvm/Support/BranchProbability.h"

   /// Returns true if the target implements the MachineOutliner.
   virtual bool useMachineOutliner() const { return false; }
 
-  /// Describes the number of instructions that it will take to call and
-  /// construct a frame for a given outlining candidate.
-  struct MachineOutlinerInfo {
-    /// Represents the size of a sequence in bytes. (Some instructions vary
-    /// widely in size, so just counting the instructions isn't very useful.)
-    unsigned SequenceSize;
-
-    /// Number of instructions to call an outlined function for this candidate.
-    unsigned CallOverhead;
-
-    /// Number of instructions to construct an outlined function frame
-    /// for this candidate.
-    unsigned FrameOverhead;
-
-    /// Represents the specific instructions that must be emitted to
-    /// construct a call to this candidate.
-    unsigned CallConstructionID;
-
-    /// Represents the specific instructions that must be emitted to
-    /// construct a frame for this candidate's outlined function.
-    unsigned FrameConstructionID;
-
-    MachineOutlinerInfo() {}
-    MachineOutlinerInfo(unsigned SequenceSize, unsigned CallOverhead,
-                        unsigned FrameOverhead, unsigned CallConstructionID,
-                        unsigned FrameConstructionID)
-        : SequenceSize(SequenceSize), CallOverhead(CallOverhead),
-          FrameOverhead(FrameOverhead),
-          CallConstructionID(CallConstructionID),
-          FrameConstructionID(FrameConstructionID) {}
-  };
-
-  /// Returns a \p MachineOutlinerInfo struct containing target-specific
+  /// Returns a \p outliner::TargetCostInfo struct containing target-specific
   /// information for a set of outlining candidates.
-  virtual MachineOutlinerInfo getOutlininingCandidateInfo(
-      std::vector<
-          std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
-          &RepeatedSequenceLocs) const {
+  virtual outliner::TargetCostInfo getOutliningCandidateInfo(
+      std::vector<outliner::Candidate> &RepeatedSequenceLocs) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::getOutliningCandidateInfo!");
   }
 
-  /// Represents how an instruction should be mapped by the outliner.
-  /// \p Legal instructions are those which are safe to outline.
-  /// \p LegalTerminator instructions are safe to outline, but only as the
-  /// last instruction in a sequence.
-  /// \p Illegal instructions are those which cannot be outlined.
-  /// \p Invisible instructions are instructions which can be outlined, but
-  /// shouldn't actually impact the outlining result.
-  enum MachineOutlinerInstrType { Legal, LegalTerminator, Illegal, Invisible };
-
   /// Returns how or if \p MI should be outlined.
-  virtual MachineOutlinerInstrType
-  getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const {
+  virtual outliner::InstrType getOutliningType(MachineBasicBlock::iterator &MIT,
+                                               unsigned Flags) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::getOutliningType!");
   }

   /// Insert a custom epilogue for outlined functions.
   /// This may be empty, in which case no epilogue or return statement will be
   /// emitted.
-  virtual void insertOutlinerEpilogue(MachineBasicBlock &MBB,
-                                      MachineFunction &MF,
-                                      const MachineOutlinerInfo &MInfo) const {
+  virtual void
+  insertOutlinerEpilogue(MachineBasicBlock &MBB, MachineFunction &MF,
+                         const outliner::TargetCostInfo &TCI) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::insertOutlinerEpilogue!");
   }

   virtual MachineBasicBlock::iterator
   insertOutlinedCall(Module &M, MachineBasicBlock &MBB,
                      MachineBasicBlock::iterator &It, MachineFunction &MF,
-                     const MachineOutlinerInfo &MInfo) const {
+                     const outliner::TargetCostInfo &TCI) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::insertOutlinedCall!");
   }
 
   /// Insert a custom prologue for outlined functions.
   /// This may be empty, in which case no prologue will be emitted.
-  virtual void insertOutlinerPrologue(MachineBasicBlock &MBB,
-                                      MachineFunction &MF,
-                                      const MachineOutlinerInfo &MInfo) const {
+  virtual void
+  insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF,
+                         const outliner::TargetCostInfo &TCI) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::insertOutlinerPrologue!");
   }

lib/CodeGen/MachineOutliner.cpp

 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
 ///
 //===----------------------------------------------------------------------===//
+#include "llvm/CodeGen/MachineOutliner.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Twine.h"

 
 using namespace llvm;
 using namespace ore;
+using namespace outliner;
 
 STATISTIC(NumOutlined, "Number of candidates outlined");
 STATISTIC(FunctionsCreated, "Number of functions created");

 // this is off by default. It should, however, be the default behaviour in
 // LTO.
 static cl::opt<bool> EnableLinkOnceODROutlining(
-    "enable-linkonceodr-outlining",
-    cl::Hidden,
+    "enable-linkonceodr-outlining", cl::Hidden,
     cl::desc("Enable the machine outliner on linkonceodr functions"),
     cl::init(false));
 
 namespace {
 
-/// An individual sequence of instructions to be replaced with a call to
-/// an outlined function.
-struct Candidate {
-private:
-  /// The start index of this \p Candidate in the instruction list.
-  unsigned StartIdx;
-
-  /// The number of instructions in this \p Candidate.
-  unsigned Len;
-
-  /// The MachineFunction containing this \p Candidate.
-  MachineFunction *MF = nullptr;
-
-public:
-  /// Set to false if the candidate overlapped with another candidate.
-  bool InCandidateList = true;
-
-  /// The index of this \p Candidate's \p OutlinedFunction in the list of
-  /// \p OutlinedFunctions.
-  unsigned FunctionIdx;
-
-  /// Contains all target-specific information for this \p Candidate.
-  TargetInstrInfo::MachineOutlinerInfo MInfo;
-
-  /// If there is a DISubprogram associated with the function that this
-  /// Candidate lives in, return it.
-  DISubprogram *getSubprogramOrNull() const {
-    assert(MF && "Candidate has no MF!");
-    if (DISubprogram *SP = MF->getFunction().getSubprogram())
-      return SP;
-    return nullptr;
-  }
-
-  /// Return the number of instructions in this Candidate.
-  unsigned getLength() const { return Len; }
-
-  /// Return the start index of this candidate.
-  unsigned getStartIdx() const { return StartIdx; }
-
-  // Return the end index of this candidate.
-  unsigned getEndIdx() const { return StartIdx + Len - 1; }
-
-  /// The number of instructions that would be saved by outlining every
-  /// candidate of this type.
-  ///
-  /// This is a fixed value which is not updated during the candidate pruning
-  /// process. It is only used for deciding which candidate to keep if two
-  /// candidates overlap. The true benefit is stored in the OutlinedFunction
-  /// for some given candidate.
-  unsigned Benefit = 0;
-
-  Candidate(unsigned StartIdx, unsigned Len, unsigned FunctionIdx,
-            MachineFunction *MF)
-      : StartIdx(StartIdx), Len(Len), MF(MF), FunctionIdx(FunctionIdx) {}
-
-  Candidate() {}
-
-  /// Used to ensure that \p Candidates are outlined in an order that
-  /// preserves the start and end indices of other \p Candidates.
-  bool operator<(const Candidate &RHS) const {
-    return getStartIdx() > RHS.getStartIdx();
-  }
-};
-
-/// The information necessary to create an outlined function for some
-/// class of candidate.
-struct OutlinedFunction {
-
-private:
-  /// The number of candidates for this \p OutlinedFunction.
-  unsigned OccurrenceCount = 0;
-
-public:
-  std::vector<std::shared_ptr<Candidate>> Candidates;
-
-  /// The actual outlined function created.
-  /// This is initialized after we go through and create the actual function.
-  MachineFunction *MF = nullptr;
-
-  /// A number assigned to this function which appears at the end of its name.
-  unsigned Name;
-
-  /// The sequence of integers corresponding to the instructions in this
-  /// function.
-  std::vector<unsigned> Sequence;
-
-  /// Contains all target-specific information for this \p OutlinedFunction.
-  TargetInstrInfo::MachineOutlinerInfo MInfo;
-
-  /// If there is a DISubprogram for any Candidate for this outlined function,
-  /// then return it. Otherwise, return nullptr.
-  DISubprogram *getSubprogramOrNull() const {
-    for (const auto &C : Candidates)
-      if (DISubprogram *SP = C->getSubprogramOrNull())
-        return SP;
-    return nullptr;
-  }
-
-  /// Return the number of candidates for this \p OutlinedFunction.
-  unsigned getOccurrenceCount() { return OccurrenceCount; }
-
-  /// Decrement the occurrence count of this OutlinedFunction and return the
-  /// new count.
-  unsigned decrement() {
-    assert(OccurrenceCount > 0 && "Can't decrement an empty function!");
-    OccurrenceCount--;
-    return getOccurrenceCount();
-  }
-
-  /// Return the number of bytes it would take to outline this
-  /// function.
-  unsigned getOutliningCost() {
-    return (OccurrenceCount * MInfo.CallOverhead) + MInfo.SequenceSize +
-           MInfo.FrameOverhead;
-  }
-
-  /// Return the size in bytes of the unoutlined sequences.
-  unsigned getNotOutlinedCost() {
-    return OccurrenceCount * MInfo.SequenceSize;
-  }
-
-  /// Return the number of instructions that would be saved by outlining
-  /// this function.
-  unsigned getBenefit() {
-    unsigned NotOutlinedCost = getNotOutlinedCost();
-    unsigned OutlinedCost = getOutliningCost();
-    return (NotOutlinedCost < OutlinedCost) ? 0
-                                            : NotOutlinedCost - OutlinedCost;
-  }
-
-  OutlinedFunction(unsigned Name, unsigned OccurrenceCount,
-                   const std::vector<unsigned> &Sequence,
-                   TargetInstrInfo::MachineOutlinerInfo &MInfo)
-      : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence),
-        MInfo(MInfo) {}
-};
-
 /// Represents an undefined index in the suffix tree.
 const unsigned EmptyIdx = -1;
 

 
       // Keep track of where this instruction is in the module.
       switch (TII.getOutliningType(It, Flags)) {
-      case TargetInstrInfo::MachineOutlinerInstrType::Illegal:
+      case InstrType::Illegal:
         mapToIllegalUnsigned(It);
         break;
 
-      case TargetInstrInfo::MachineOutlinerInstrType::Legal:
+      case InstrType::Legal:
         mapToLegalUnsigned(It);
         break;
 
-      case TargetInstrInfo::MachineOutlinerInstrType::LegalTerminator:
+      case InstrType::LegalTerminator:
         mapToLegalUnsigned(It);
         InstrList.push_back(It);
         UnsignedVec.push_back(IllegalInstrNumber);
         IllegalInstrNumber--;
         break;
 
-      case TargetInstrInfo::MachineOutlinerInstrType::Invisible:
+      case InstrType::Invisible:
         break;
       }
     }

   /// Construct a suffix tree on the instructions in \p M and outline repeated
   /// strings from that tree.
   bool runOnModule(Module &M) override;
+
+  /// Return a DISubprogram for OF if one exists, and null otherwise. Helper
+  /// function for remark emission.
+  DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {
+    DISubprogram *SP;
+    for (const std::shared_ptr<Candidate> &C : OF.Candidates)
+      if (C && C->getMF() && (SP = C->getMF()->getFunction().getSubprogram()))
+        return SP;
+    return nullptr;
+  }
 };
 
 } // Anonymous namespace.

 char MachineOutliner::ID = 0;
 
 namespace llvm {
-ModulePass *createMachineOutlinerPass() {
-  return new MachineOutliner();
-}
+ModulePass *createMachineOutlinerPass() { return new MachineOutliner(); }
 
 } // namespace llvm
 

     // this vector.
     std::vector<Candidate> CandidatesForRepeatedSeq;
 
-    // Describes the start and end point of each candidate. This allows the
-    // target to infer some information about each occurrence of each repeated
-    // sequence.
-    // FIXME: CandidatesForRepeatedSeq and this should be combined.
-    std::vector<
-        std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
-        RepeatedSequenceLocs;
-
     // Figure out the call overhead for each instance of the sequence.
     for (auto &ChildPair : Parent.Children) {
       SuffixTreeNode *M = ChildPair.second;

         // AA (where each "A" is an instruction).
         //
         // We might have some portion of the module that looks like this:
-        // AAAAAA (6 A's) 
+        // AAAAAA (6 A's)
         //
         // In this case, there are 5 different copies of "AA" in this range, but
         // at most 3 can be outlined. If only outlining 3 of these is going to

                         CandidatesForRepeatedSeq.end(),
                         [&StartIdx, &EndIdx](const Candidate &C) {
                           return (EndIdx < C.getStartIdx() ||
-                                  StartIdx > C.getEndIdx()); 
+                                  StartIdx > C.getEndIdx());
                         })) {
           // It doesn't overlap with anything, so we can outline it.
-          // Each sequence is over [StartIt, EndIt].
+          // Each sequence is over [StartIt, EndIt]. Save the candidate and its
+          // location.
           MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
           MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
-
-          // Save the MachineFunction containing the Candidate.
-          MachineFunction *MF = StartIt->getParent()->getParent();
-          assert(MF && "Candidate doesn't have a MF?");
-
-          // Save the candidate and its location.
-          CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen,
-                                                FunctionList.size(), MF);
-          RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt));
+          CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt,
+                                                EndIt, StartIt->getParent(),
+                                                FunctionList.size());
         }
       }
     }

     // We've found something we might want to outline.
     // Create an OutlinedFunction to store it and check if it'd be beneficial
     // to outline.
-    TargetInstrInfo::MachineOutlinerInfo MInfo =
-        TII.getOutlininingCandidateInfo(RepeatedSequenceLocs);
+    TargetCostInfo TCI =
+                      TII.getOutliningCandidateInfo(CandidatesForRepeatedSeq);
     std::vector<unsigned> Seq;
     for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++)
       Seq.push_back(ST.Str[i]);
     OutlinedFunction OF(FunctionList.size(), CandidatesForRepeatedSeq.size(),
-                        Seq, MInfo);
+                        Seq, TCI);
     unsigned Benefit = OF.getBenefit();
 
     // Is it better to outline this candidate than not?

       // Outlining this candidate would take more instructions than not
       // outlining.
       // Emit a remark explaining why we didn't outline this candidate.
-      std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator> C =
-          RepeatedSequenceLocs[0];
-      MachineOptimizationRemarkEmitter MORE(
-          *(C.first->getParent()->getParent()), nullptr);
+      Candidate &C = CandidatesForRepeatedSeq.front();
+      MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr);
       MORE.emit([&]() {
         MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
-                                          C.first->getDebugLoc(),
-                                          C.first->getParent());
+                                          C.front()->getDebugLoc(), C.getMBB());
         R << "Did not outline " << NV("Length", StringLen) << " instructions"
-          << " from " << NV("NumOccurrences", RepeatedSequenceLocs.size())
+          << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size())
           << " locations."
           << " Bytes from outlining all occurrences ("
           << NV("OutliningCost", OF.getOutliningCost()) << ")"

           << " (Also found at: ";
 
         // Tell the user the other places the candidate was found.
-        for (unsigned i = 1, e = RepeatedSequenceLocs.size(); i < e; i++) {
+        for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) {
           R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
-                  RepeatedSequenceLocs[i].first->getDebugLoc());
+                  CandidatesForRepeatedSeq[i].front()->getDebugLoc());
           if (i != e - 1)
             R << ", ";
         }

     // At this point, the candidate class is seen as beneficial. Set their
     // benefit values and save them in the candidate list.
     std::vector<std::shared_ptr<Candidate>> CandidatesForFn;
+
     for (Candidate &C : CandidatesForRepeatedSeq) {
       C.Benefit = Benefit;
-      C.MInfo = MInfo;
+      C.TCI = TCI;
       std::shared_ptr<Candidate> Cptr = std::make_shared<Candidate>(C);
       CandidateList.push_back(Cptr);
       CandidatesForFn.push_back(Cptr);

   // Return true if this candidate became unbeneficial for outlining in a
   // previous step.
   auto ShouldSkipCandidate = [&FunctionList, this](Candidate &C) {
-
     // Check if the candidate was removed in a previous step.
     if (!C.InCandidateList)
       return true;

   // Insert the new function into the module.
   MF.insert(MF.begin(), &MBB);
 
-  TII.insertOutlinerPrologue(MBB, MF, OF.MInfo);
+  TII.insertOutlinerPrologue(MBB, MF, OF.TCI);
 
   // Copy over the instructions for the function using the integer mappings in
   // its sequence.

     MBB.insert(MBB.end(), NewMI);
   }
 
-  TII.insertOutlinerEpilogue(MBB, MF, OF.MInfo);
+  TII.insertOutlinerEpilogue(MBB, MF, OF.TCI);
 
   // If there's a DISubprogram associated with this outlined function, then
   // emit debug info for the outlined function.
-  if (DISubprogram *SP = OF.getSubprogramOrNull()) {
+  if (DISubprogram *SP = getSubprogramOrNull(OF)) {
     // We have a DISubprogram. Get its DICompileUnit.
     DICompileUnit *CU = SP->getUnit();
     DIBuilder DB(M, true, CU);

   bool OutlinedSomething = false;
   // Replace the candidates with calls to their respective outlined functions.
   for (const std::shared_ptr<Candidate> &Cptr : CandidateList) {
-    Candidate &C = *Cptr;
+
     // Was the candidate removed during pruneOverlaps?
-    if (!C.InCandidateList)
+    if (!Cptr || !Cptr->InCandidateList)
       continue;
+    Candidate &C = *Cptr;
 
     // If not, then look at its OutlinedFunction.
     OutlinedFunction &OF = FunctionList[C.FunctionIdx];

     if (OF.getBenefit() < 1)
       continue;
 
-    // If not, then outline it.
-    assert(C.getStartIdx() < Mapper.InstrList.size() &&
-           "Candidate out of bounds!");
-    MachineBasicBlock *MBB = (*Mapper.InstrList[C.getStartIdx()]).getParent();
-    MachineBasicBlock::iterator StartIt = Mapper.InstrList[C.getStartIdx()];
-    unsigned EndIdx = C.getEndIdx();
-
-    assert(EndIdx < Mapper.InstrList.size() && "Candidate out of bounds!");
-    MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
-    assert(EndIt != MBB->end() && "EndIt out of bounds!");
-
     // Does this candidate have a function yet?
     if (!OF.MF) {
       OF.MF = createOutlinedFunction(M, OF, Mapper);
-      MachineBasicBlock *MBB = &*OF.MF->begin();
+      MachineBasicBlock *NewMBB = &*OF.MF->begin();
 
       // Output a remark telling the user that an outlined function was created,
       // and explaining where it came from.
       MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
       MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
-                                  MBB->findDebugLoc(MBB->begin()), MBB);
-      R << "Saved " << NV("OutliningBenefit", OF.getBenefit())
-        << " bytes by "
+                                  NewMBB->findDebugLoc(NewMBB->begin()),
+                                  NewMBB);
+      R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "
         << "outlining " << NV("Length", OF.Sequence.size()) << " instructions "
         << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
         << " locations. "

         if (!OF.Candidates[i]->InCandidateList)
           continue;
 
-        R << NV(
-            (Twine("StartLoc") + Twine(i)).str(),
-            Mapper.InstrList[OF.Candidates[i]->getStartIdx()]->getDebugLoc());
+        R << NV((Twine("StartLoc") + Twine(i)).str(),
+                OF.Candidates[i]->front()->getDebugLoc());
         if (i != e - 1)
           R << ", ";
       }

       FunctionsCreated++;
     }
 
+    // Outline it.
+    MachineBasicBlock &MBB = *C.getMBB();
     MachineFunction *MF = OF.MF;
+    MachineBasicBlock::iterator StartIt = C.front();
+    MachineBasicBlock::iterator EndIt = C.back();
+    assert(StartIt != C.getMBB()->end() && "StartIt out of bounds!");
+    assert(EndIt != C.getMBB()->end() && "EndIt out of bounds!");
+
     const TargetSubtargetInfo &STI = MF->getSubtarget();
     const TargetInstrInfo &TII = *STI.getInstrInfo();
 
     // Insert a call to the new function and erase the old sequence.
-    auto CallInst = TII.insertOutlinedCall(M, *MBB, StartIt, *MF, C.MInfo);
-    StartIt = Mapper.InstrList[C.getStartIdx()];
+    auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *OF.MF, C.TCI);
 
     // If the caller tracks liveness, then we need to make sure that anything
     // we outline doesn't break liveness assumptions.
     // The outlined functions themselves currently don't track liveness, but
     // we should make sure that the ranges we yank things out of aren't
     // wrong.
-    if (MBB->getParent()->getProperties().hasProperty(
+    if (MBB.getParent()->getProperties().hasProperty(
             MachineFunctionProperties::Property::TracksLiveness)) {
       // Helper lambda for adding implicit def operands to the call instruction.
       auto CopyDefs = [&CallInst](MachineInstr &MI) {

       std::for_each(CallInst, EndIt, CopyDefs);
     }
 
-    EndIt++; // Erase needs one past the end index.
-    MBB->erase(StartIt, EndIt);
+    // Erase from the point after where the call was inserted up to, and
+    // including, the final instruction in the sequence.
+    // Erase needs one past the end, so we need std::next there too.
+    MBB.erase(std::next(StartIt), std::next(EndIt));
     OutlinedSomething = true;
 
     // Statistics.

lib/Target/AArch64/AArch64InstrInfo.h

   canOutlineWithoutLRSave(MachineBasicBlock::iterator &CallInsertionPt) const;
   bool isFunctionSafeToOutlineFrom(MachineFunction &MF,
                                    bool OutlineFromLinkOnceODRs) const override;
-  MachineOutlinerInfo getOutlininingCandidateInfo(
-      std::vector<
-          std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
-          &RepeatedSequenceLocs) const override;
-  AArch64GenInstrInfo::MachineOutlinerInstrType
-  getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const override;
+  outliner::TargetCostInfo getOutliningCandidateInfo(
+      std::vector<outliner::Candidate> &RepeatedSequenceLocs) const override;
+  outliner::InstrType getOutliningType(MachineBasicBlock::iterator &MIT,
+                                       unsigned Flags) const override;
   unsigned getMachineOutlinerMBBFlags(MachineBasicBlock &MBB) const override;
-  void insertOutlinerEpilogue(MachineBasicBlock &MBB, MachineFunction &MF,
-                              const MachineOutlinerInfo &MInfo) const override;
-  void insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF,
-                              const MachineOutlinerInfo &MInfo) const override;
+  void
+  insertOutlinerEpilogue(MachineBasicBlock &MBB, MachineFunction &MF,
+                         const outliner::TargetCostInfo &TCI) const override;
+  void
+  insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF,
+                         const outliner::TargetCostInfo &TCI) const override;
   MachineBasicBlock::iterator
   insertOutlinedCall(Module &M, MachineBasicBlock &MBB,
                      MachineBasicBlock::iterator &It, MachineFunction &MF,
-                     const MachineOutlinerInfo &MInfo) const override;
+                     const outliner::TargetCostInfo &TCI) const override;
   /// Returns true if the instruction sets to an immediate value that can be
   /// executed more efficiently.
   bool isExynosResetFast(const MachineInstr &MI) const;

lib/Target/AArch64/AArch64InstrInfo.cpp

   return LRU.available(AArch64::LR);
 }
 
-AArch64GenInstrInfo::MachineOutlinerInfo
-AArch64InstrInfo::getOutlininingCandidateInfo(
-    std::vector<
-        std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
-        &RepeatedSequenceLocs) const {
-  unsigned SequenceSize = std::accumulate(
-      RepeatedSequenceLocs[0].first, std::next(RepeatedSequenceLocs[0].second),
-      0, [this](unsigned Sum, const MachineInstr &MI) {
-        return Sum + getInstSizeInBytes(MI);
-      });
+outliner::TargetCostInfo AArch64InstrInfo::getOutliningCandidateInfo(
+    std::vector<outliner::Candidate> &RepeatedSequenceLocs) const {
+  unsigned SequenceSize =
+      std::accumulate(RepeatedSequenceLocs[0].front(),
+                      std::next(RepeatedSequenceLocs[0].back()), 0,
+                      [this](unsigned Sum, const MachineInstr &MI) {
+                        return Sum + getInstSizeInBytes(MI);
+                      });
   unsigned CallID = MachineOutlinerDefault;
   unsigned FrameID = MachineOutlinerDefault;
   unsigned NumBytesForCall = 12;
   unsigned NumBytesToCreateFrame = 4;
 
-  auto DoesntNeedLRSave =
-      [this](std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>
-                 &I) { return canOutlineWithoutLRSave(I.second); };
+  auto DoesntNeedLRSave = [this](outliner::Candidate &I) {
+    return canOutlineWithoutLRSave(I.back());
+  };
 
-  unsigned LastInstrOpcode = RepeatedSequenceLocs[0].second->getOpcode();
+  unsigned LastInstrOpcode = RepeatedSequenceLocs[0].back()->getOpcode();
 
   // If the last instruction in any candidate is a terminator, then we should
   // tail call all of the candidates.
-  if (RepeatedSequenceLocs[0].second->isTerminator()) {
+  if (RepeatedSequenceLocs[0].back()->isTerminator()) {
     CallID = MachineOutlinerTailCall;
     FrameID = MachineOutlinerTailCall;
     NumBytesForCall = 4;

 
   // Check if the range contains a call. These require a save + restore of the
   // link register.
-  if (std::any_of(RepeatedSequenceLocs[0].first, RepeatedSequenceLocs[0].second,
+  if (std::any_of(RepeatedSequenceLocs[0].front(),
+                  RepeatedSequenceLocs[0].back(),
                   [](const MachineInstr &MI) { return MI.isCall(); }))
     NumBytesToCreateFrame += 8; // Save + restore the link register.
 

   // it being valid to tail call this sequence. We should consider this as well.
   else if (FrameID != MachineOutlinerThunk &&
            FrameID != MachineOutlinerTailCall &&
-           RepeatedSequenceLocs[0].second->isCall())
+           RepeatedSequenceLocs[0].back()->isCall())
     NumBytesToCreateFrame += 8;
 
-  return MachineOutlinerInfo(SequenceSize, NumBytesForCall,
+  return outliner::TargetCostInfo(SequenceSize, NumBytesForCall,
                                   NumBytesToCreateFrame, CallID, FrameID);
 }
 
 bool AArch64InstrInfo::isFunctionSafeToOutlineFrom(

   LiveRegUnits LRU(getRegisterInfo());
   LRU.addLiveOuts(MBB);
 
-  std::for_each(MBB.rbegin(),
-                MBB.rend(),
+  std::for_each(MBB.rbegin(), MBB.rend(),
                 [&LRU](MachineInstr &MI) { LRU.accumulate(MI); });
 
-  if (!LRU.available(AArch64::LR)) 
-      Flags |= MachineOutlinerMBBFlags::LRUnavailableSomewhere;
+  if (!LRU.available(AArch64::LR))
 
   return Flags;
 }
 
-AArch64GenInstrInfo::MachineOutlinerInstrType
+outliner::InstrType
 AArch64InstrInfo::getOutliningType(MachineBasicBlock::iterator &MIT,
                                    unsigned Flags) const {
   MachineInstr &MI = *MIT;

 
   // Don't outline LOHs.
   if (FuncInfo->getLOHRelated().count(&MI))
-    return MachineOutlinerInstrType::Illegal;
+    return outliner::InstrType::Illegal;
 
   // Don't allow debug values to impact outlining type.
   if (MI.isDebugInstr() || MI.isIndirectDebugValue())
-    return MachineOutlinerInstrType::Invisible;
+    return outliner::InstrType::Invisible;
 
   // At this point, KILL instructions don't really tell us much so we can go
   // ahead and skip over them.
   if (MI.isKill())
-    return MachineOutlinerInstrType::Invisible;
-  
+    return outliner::InstrType::Invisible;
   // Is this a terminator for a basic block?
   if (MI.isTerminator()) {
 
     // Is this the end of a function?
     if (MI.getParent()->succ_empty())
-      return MachineOutlinerInstrType::Legal;
-    
+      return outliner::InstrType::Legal;
     // It's not, so don't outline it.
-    return MachineOutlinerInstrType::Illegal;
+    return outliner::InstrType::Illegal;
   }
 
   // Make sure none of the operands are un-outlinable.
   for (const MachineOperand &MOP : MI.operands()) {
     if (MOP.isCPI() || MOP.isJTI() || MOP.isCFIIndex() || MOP.isFI() ||
         MOP.isTargetIndex())
-      return MachineOutlinerInstrType::Illegal;
+      return outliner::InstrType::Illegal;
 
     // If it uses LR or W30 explicitly, then don't touch it.
     if (MOP.isReg() && !MOP.isImplicit() &&
         (MOP.getReg() == AArch64::LR || MOP.getReg() == AArch64::W30))
-      return MachineOutlinerInstrType::Illegal;
+      return outliner::InstrType::Illegal;
   }
 
   // Special cases for instructions that can always be outlined, but will fail
   // the later tests. e.g, ADRPs, which are PC-relative use LR, but can always
   // be outlined because they don't require a *specific* value to be in LR.
   if (MI.getOpcode() == AArch64::ADRP)
-    return MachineOutlinerInstrType::Legal;
+    return outliner::InstrType::Legal;
 
   // If MI is a call we might be able to outline it. We don't want to outline
   // any calls that rely on the position of items on the stack. When we outline

     // Never outline calls to mcount.  There isn't any rule that would require
     // this, but the Linux kernel's "ftrace" feature depends on it.
     if (Callee && Callee->getName() == "\01_mcount")
-      return MachineOutlinerInstrType::Illegal;
+      return outliner::InstrType::Illegal;
 
     // If we don't know anything about the callee, assume it depends on the
     // stack layout of the caller. In that case, it's only legal to outline
     // as a tail-call.  Whitelist the call instructions we know about so we
     // don't get unexpected results with call pseudo-instructions.
-    auto UnknownCallOutlineType = MachineOutlinerInstrType::Illegal;
+    auto UnknownCallOutlineType = outliner::InstrType::Illegal;
     if (MI.getOpcode() == AArch64::BLR || MI.getOpcode() == AArch64::BL)
-      UnknownCallOutlineType = MachineOutlinerInstrType::LegalTerminator;
+      UnknownCallOutlineType = outliner::InstrType::LegalTerminator;
 
     if (!Callee)
       return UnknownCallOutlineType;

 
     // At this point, we can say that CalleeMF ought to not pass anything on the
     // stack. Therefore, we can outline it.
-    return MachineOutlinerInstrType::Legal;
+    return outliner::InstrType::Legal;
   }
 
   // Don't outline positions.
   if (MI.isPosition())
-    return MachineOutlinerInstrType::Illegal;
+    return outliner::InstrType::Illegal;
 
   // Don't touch the link register or W30.
   if (MI.readsRegister(AArch64::W30, &getRegisterInfo()) ||
       MI.modifiesRegister(AArch64::W30, &getRegisterInfo()))
-    return MachineOutlinerInstrType::Illegal;
+    return outliner::InstrType::Illegal;
 
   // Does this use the stack?
   if (MI.modifiesRegister(AArch64::SP, &RI) ||

     // SUBXris are extremely common in prologue/epilogue code, so supporting
     // them in the outliner can be a pretty big win!
     if (!MightNeedStackFixUp)
-      return MachineOutlinerInstrType::Legal;
+      return outliner::InstrType::Legal;
 
     // Any modification of SP will break our code to save/restore LR.
     // FIXME: We could handle some instructions which add a constant offset to
     // SP, with a bit more work.
     if (MI.modifiesRegister(AArch64::SP, &RI))
-      return MachineOutlinerInstrType::Illegal;
+      return outliner::InstrType::Illegal;
 
     // At this point, we have a stack instruction that we might need to fix
     // up. We'll handle it if it's a load or store.

       // Does it allow us to offset the base register and is the base SP?
       if (!getMemOpBaseRegImmOfsWidth(MI, Base, Offset, DummyWidth, &RI) ||
           Base != AArch64::SP)
-        return MachineOutlinerInstrType::Illegal;
+        return outliner::InstrType::Illegal;
 
       // Find the minimum/maximum offset for this instruction and check if
       // fixing it up would be in range.

       // to a MIR test, it really ought to be checked.
       Offset += 16; // Update the offset to what it would be if we outlined.
       if (Offset < MinOffset * Scale || Offset > MaxOffset * Scale)
-        return MachineOutlinerInstrType::Illegal;
+        return outliner::InstrType::Illegal;
 
       // It's in range, so we can outline it.
-      return MachineOutlinerInstrType::Legal;
+      return outliner::InstrType::Legal;
     }
 
     // FIXME: Add handling for instructions like "add x0, sp, #8".
 
     // We can't fix it up, so don't outline it.
-    return MachineOutlinerInstrType::Illegal;
+    return outliner::InstrType::Illegal;
   }
 
-  return MachineOutlinerInstrType::Legal;
+  return outliner::InstrType::Legal;
 }
 
 void AArch64InstrInfo::fixupPostOutline(MachineBasicBlock &MBB) const {

 
 void AArch64InstrInfo::insertOutlinerEpilogue(
     MachineBasicBlock &MBB, MachineFunction &MF,
-    const MachineOutlinerInfo &MInfo) const {
+    const outliner::TargetCostInfo &TCI) const {
   // For thunk outlining, rewrite the last instruction from a call to a
   // tail-call.
-  if (MInfo.FrameConstructionID == MachineOutlinerThunk) {
+  if (TCI.FrameConstructionID == MachineOutlinerThunk) {
     MachineInstr *Call = &*--MBB.instr_end();
     unsigned TailOpcode;
     if (Call->getOpcode() == AArch64::BL) {

       TailOpcode = AArch64::TCRETURNri;
     }
     MachineInstr *TC = BuildMI(MF, DebugLoc(), get(TailOpcode))
-                            .add(Call->getOperand(0))
-                            .addImm(0);
     MBB.insert(MBB.end(), TC);
     Call->eraseFromParent();
   }

   if (std::any_of(MBB.instr_begin(), MBB.instr_end(), IsNonTailCall)) {
     // Fix up the instructions in the range, since we're going to modify the
     // stack.
-    assert(MInfo.FrameConstructionID != MachineOutlinerDefault &&
+    assert(TCI.FrameConstructionID != MachineOutlinerDefault &&
            "Can only fix up stack references once");
     fixupPostOutline(MBB);
 

     MachineBasicBlock::iterator It = MBB.begin();
     MachineBasicBlock::iterator Et = MBB.end();
 
-    if (MInfo.FrameConstructionID == MachineOutlinerTailCall ||
-        MInfo.FrameConstructionID == MachineOutlinerThunk)
+    if (TCI.FrameConstructionID == MachineOutlinerTailCall ||
+        TCI.FrameConstructionID == MachineOutlinerThunk)
       Et = std::prev(MBB.end());
 
     // Insert a save before the outlined region

   }
 
   // If this is a tail call outlined function, then there's already a return.
-  if (MInfo.FrameConstructionID == MachineOutlinerTailCall ||
-      MInfo.FrameConstructionID == MachineOutlinerThunk)
+  if (TCI.FrameConstructionID == MachineOutlinerTailCall ||
+      TCI.FrameConstructionID == MachineOutlinerThunk)
     return;
 
   // It's not a tail call, so we have to insert the return ourselves.

   MBB.insert(MBB.end(), ret);
 
   // Did we have to modify the stack by saving the link register?
-  if (MInfo.FrameConstructionID == MachineOutlinerNoLRSave)
+  if (TCI.FrameConstructionID == MachineOutlinerNoLRSave)
     return;
 
   // We modified the stack.

 
 void AArch64InstrInfo::insertOutlinerPrologue(
     MachineBasicBlock &MBB, MachineFunction &MF,
-    const MachineOutlinerInfo &MInfo) const {}
+    const outliner::TargetCostInfo &TCI) const {}
 
 MachineBasicBlock::iterator AArch64InstrInfo::insertOutlinedCall(
     Module &M, MachineBasicBlock &MBB, MachineBasicBlock::iterator &It,
-    MachineFunction &MF, const MachineOutlinerInfo &MInfo) const {
+    MachineFunction &MF, const outliner::TargetCostInfo &TCI) const {
 
   // Are we tail calling?
-  if (MInfo.CallConstructionID == MachineOutlinerTailCall) {
+  if (TCI.CallConstructionID == MachineOutlinerTailCall) {
     // If yes, then we can just branch to the label.
     It = MBB.insert(It, BuildMI(MF, DebugLoc(), get(AArch64::TCRETURNdi))
                             .addGlobalAddress(M.getNamedValue(MF.getName()))

   }
 
   // Are we saving the link register?
-  if (MInfo.CallConstructionID == MachineOutlinerNoLRSave ||
-      MInfo.CallConstructionID == MachineOutlinerThunk) {
+  if (TCI.CallConstructionID == MachineOutlinerNoLRSave ||
+      TCI.CallConstructionID == MachineOutlinerThunk) {
     // No, so just insert the call.
     It = MBB.insert(It, BuildMI(MF, DebugLoc(), get(AArch64::BL))
                             .addGlobalAddress(M.getNamedValue(MF.getName())));

lib/Target/X86/X86InstrInfo.h

   /// X86 supports the MachineOutliner.
   bool useMachineOutliner() const override { return true; }
 
-  virtual MachineOutlinerInfo getOutlininingCandidateInfo(
-      std::vector<
-          std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
-          &RepeatedSequenceLocs) const override;
+  virtual outliner::TargetCostInfo getOutliningCandidateInfo(
+      std::vector<outliner::Candidate> &RepeatedSequenceLocs) const override;
 
   bool isFunctionSafeToOutlineFrom(MachineFunction &MF,
                                    bool OutlineFromLinkOnceODRs) const override;
 
-  llvm::X86GenInstrInfo::MachineOutlinerInstrType
-  getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const override;
+  outliner::InstrType getOutliningType(MachineBasicBlock::iterator &MIT,
+                                       unsigned Flags) const override;
 
-  void insertOutlinerEpilogue(MachineBasicBlock &MBB, MachineFunction &MF,
-                              const MachineOutlinerInfo &MInfo) const override;
+  void
+  insertOutlinerEpilogue(MachineBasicBlock &MBB, MachineFunction &MF,
+                         const outliner::TargetCostInfo &TCI) const override;
 
-  void insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF,
-                              const MachineOutlinerInfo &MInfo) const override;
+  void
+  insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF,
+                         const outliner::TargetCostInfo &TCI) const override;
 
   MachineBasicBlock::iterator
   insertOutlinedCall(Module &M, MachineBasicBlock &MBB,
                      MachineBasicBlock::iterator &It, MachineFunction &MF,
-                     const MachineOutlinerInfo &MInfo) const override;
+                     const outliner::TargetCostInfo &TCI) const override;
 
 protected:
   /// Commutes the operands in the given instruction by changing the operands

lib/Target/X86/X86InstrInfo.cpp

   MachineOutlinerTailCall
 };
 
-X86GenInstrInfo::MachineOutlinerInfo
-X86InstrInfo::getOutlininingCandidateInfo(
-  std::vector<
-      std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
-      &RepeatedSequenceLocs) const {
-  unsigned SequenceSize = std::accumulate(
-      RepeatedSequenceLocs[0].first, std::next(RepeatedSequenceLocs[0].second),
-      0, [](unsigned Sum, const MachineInstr &MI) {
-        // FIXME: x86 doesn't implement getInstSizeInBytes, so we can't
-        // tell the cost.  Just assume each instruction is one byte.
-        if (MI.isDebugInstr() || MI.isKill())
-          return Sum;
-        return Sum + 1;
-      });
+outliner::TargetCostInfo X86InstrInfo::getOutliningCandidateInfo(
+    std::vector<outliner::Candidate> &RepeatedSequenceLocs) const {
+  unsigned SequenceSize =
+      std::accumulate(RepeatedSequenceLocs[0].front(),
+                      std::next(RepeatedSequenceLocs[0].back()), 0,
+                      [](unsigned Sum, const MachineInstr &MI) {
+                        // FIXME: x86 doesn't implement getInstSizeInBytes, so
+                        // we can't tell the cost.  Just assume each instruction
+                        // is one byte.
+                        if (MI.isDebugInstr() || MI.isKill())
+                          return Sum;
+                        return Sum + 1;
+                      });
 
   // FIXME: Use real size in bytes for call and ret instructions.
-  if (RepeatedSequenceLocs[0].second->isTerminator())
-    return MachineOutlinerInfo(SequenceSize,
+  if (RepeatedSequenceLocs[0].back()->isTerminator())
+    return outliner::TargetCostInfo(SequenceSize,
                                1, // Number of bytes to emit call.
                                0, // Number of bytes to emit frame.
                                MachineOutlinerTailCall, // Type of call.
                                MachineOutlinerTailCall // Type of frame.
                               );
 
-  return MachineOutlinerInfo(SequenceSize, 1, 1, MachineOutlinerDefault,
+  return outliner::TargetCostInfo(SequenceSize, 1, 1, MachineOutlinerDefault,
                              MachineOutlinerDefault);
 }
 

   return true;
 }
 
-X86GenInstrInfo::MachineOutlinerInstrType
-X86InstrInfo::getOutliningType(MachineBasicBlock::iterator &MIT,  unsigned Flags) const {
+outliner::InstrType
+X86InstrInfo::getOutliningType(MachineBasicBlock::iterator &MIT,
+                               unsigned Flags) const {
   MachineInstr &MI = *MIT;
   // Don't allow debug values to impact outlining type.
   if (MI.isDebugInstr() || MI.isIndirectDebugValue())
-    return MachineOutlinerInstrType::Invisible;
+    return outliner::InstrType::Invisible;
 
   // At this point, KILL instructions don't really tell us much so we can go
   // ahead and skip over them.
   if (MI.isKill())
-    return MachineOutlinerInstrType::Invisible;
+    return outliner::InstrType::Invisible;
 
   // Is this a tail call? If yes, we can outline as a tail call.
   if (isTailCall(MI))
-    return MachineOutlinerInstrType::Legal;
+    return outliner::InstrType::Legal;
 
   // Is this the terminator of a basic block?
   if (MI.isTerminator() || MI.isReturn()) {
 
     // Does its parent have any successors in its MachineFunction?
     if (MI.getParent()->succ_empty())
-        return MachineOutlinerInstrType::Legal;
+      return outliner::InstrType::Legal;
 
     // It does, so we can't tail call it.
-    return MachineOutlinerInstrType::Illegal;
+    return outliner::InstrType::Illegal;
   }
 
   // Don't outline anything that modifies or reads from the stack pointer.

   if (MI.modifiesRegister(X86::RSP, &RI) || MI.readsRegister(X86::RSP, &RI) ||
       MI.getDesc().hasImplicitUseOfPhysReg(X86::RSP) ||
       MI.getDesc().hasImplicitDefOfPhysReg(X86::RSP))
-    return MachineOutlinerInstrType::Illegal;
+    return outliner::InstrType::Illegal;
 
   // Outlined calls change the instruction pointer, so don't read from it.
   if (MI.readsRegister(X86::RIP, &RI) ||
       MI.getDesc().hasImplicitUseOfPhysReg(X86::RIP) ||
       MI.getDesc().hasImplicitDefOfPhysReg(X86::RIP))
-    return MachineOutlinerInstrType::Illegal;
+    return outliner::InstrType::Illegal;
 
   // Positions can't safely be outlined.
   if (MI.isPosition())
-    return MachineOutlinerInstrType::Illegal;
+    return outliner::InstrType::Illegal;
 
   // Make sure none of the operands of this instruction do anything tricky.
   for (const MachineOperand &MOP : MI.operands())
     if (MOP.isCPI() || MOP.isJTI() || MOP.isCFIIndex() || MOP.isFI() ||
         MOP.isTargetIndex())
-      return MachineOutlinerInstrType::Illegal;
+      return outliner::InstrType::Illegal;
 
-  return MachineOutlinerInstrType::Legal;
+  return outliner::InstrType::Legal;
 }
 
-void X86InstrInfo::insertOutlinerEpilogue(MachineBasicBlock &MBB,
-                                          MachineFunction &MF,
-                                          const MachineOutlinerInfo &MInfo)
-                                          const {
+void X86InstrInfo::insertOutlinerEpilogue(
+    MachineBasicBlock &MBB, MachineFunction &MF,
+    const outliner::TargetCostInfo &TCI) const {
   // If we're a tail call, we already have a return, so don't do anything.
-  if (MInfo.FrameConstructionID == MachineOutlinerTailCall)
+  if (TCI.FrameConstructionID == MachineOutlinerTailCall)
     return;
 
   // We're a normal call, so our sequence doesn't have a return instruction.

   MBB.insert(MBB.end(), retq);
 }
 
-void X86InstrInfo::insertOutlinerPrologue(MachineBasicBlock &MBB,
-                                          MachineFunction &MF,
-                                          const MachineOutlinerInfo &MInfo)
-                                          const {}
+void X86InstrInfo::insertOutlinerPrologue(
+    MachineBasicBlock &MBB, MachineFunction &MF,
+    const outliner::TargetCostInfo &TCI) const {}
 
-MachineBasicBlock::iterator
-X86InstrInfo::insertOutlinedCall(Module &M, MachineBasicBlock &MBB,
-                                 MachineBasicBlock::iterator &It,
-                                 MachineFunction &MF,
-                                 const MachineOutlinerInfo &MInfo) const {
+MachineBasicBlock::iterator X86InstrInfo::insertOutlinedCall(
+    Module &M, MachineBasicBlock &MBB, MachineBasicBlock::iterator &It,
+    MachineFunction &MF, const outliner::TargetCostInfo &TCI) const {
   // Is it a tail call?
-  if (MInfo.CallConstructionID == MachineOutlinerTailCall) {
+  if (TCI.CallConstructionID == MachineOutlinerTailCall) {
     // Yes, just insert a JMP.
-    It = MBB.insert(It,
-                  BuildMI(MF, DebugLoc(), get(X86::JMP_1))
-                      .addGlobalAddress(M.getNamedValue(MF.getName())));
+    It = MBB.insert(It, BuildMI(MF, DebugLoc(), get(X86::JMP_1))
+                            .addGlobalAddress(M.getNamedValue(MF.getName())));
   } else {
     // No, insert a call.
-    It = MBB.insert(It,
-                  BuildMI(MF, DebugLoc(), get(X86::CALL64pcrel32))
-                      .addGlobalAddress(M.getNamedValue(MF.getName())));
+    It = MBB.insert(It, BuildMI(MF, DebugLoc(), get(X86::CALL64pcrel32))
+                            .addGlobalAddress(M.getNamedValue(MF.getName())));
   }
 
   return It;