[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

include/llvm/CodeGen/TargetInstrInfo.h

 #include "llvm/ADT/None.h"
 #include "llvm/CodeGen/LiveRegUnits.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineCombinerPattern.h"
 #include "llvm/CodeGen/MachineFunction.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"
 #include "llvm/Support/ErrorHandling.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <utility>
public:
   /// to prevent register allocator to insert spills before such instructions.
   virtual bool isBasicBlockPrologue(const MachineInstr &MI) const {
     return false;
   }
 
   /// 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 getOutlininingCandidateInfo(
+      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
+  virtual outliner::InstrType
   getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::getOutliningType!");
   }
 
   /// Returns target-defined flags defining properties of the MBB for
   /// the outliner.
   virtual unsigned getMachineOutlinerMBBFlags(MachineBasicBlock &MBB) const {
     return 0x0;
   }
 
   /// 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 {
+                                    const outliner::TargetCostInfo &TCI) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::insertOutlinerEpilogue!");
   }
 
   /// Insert a call to an outlined function into the program.
   /// Returns an iterator to the spot where we inserted the call. This must be
   /// implemented by the target.
   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 {
+                                    const outliner::TargetCostInfo &TCI) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::insertOutlinerPrologue!");
   }
 
   /// Return true if the function can safely be outlined from.
   /// A function \p MF is considered safe for outlining if an outlined function
   /// produced from instructions in F will produce a program which produces the
   /// same output for any set of given inputs.

lib/CodeGen/MachineOutliner.cpp

 /// For the original RFC for this pass, please see
 ///
 /// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html
 ///
 /// For more information on the suffix tree data structure, please see
 /// 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"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"

 #include <sstream>
 #include <tuple>
 #include <vector>
 
 #define DEBUG_TYPE "machine-outliner"
 
 using namespace llvm;
 using namespace ore;
+using namespace outliner;
 
 STATISTIC(NumOutlined, "Number of candidates outlined");
 STATISTIC(FunctionsCreated, "Number of functions created");
 
 // Set to true if the user wants the 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 behaviour in
 // LTO.
 static cl::opt<bool> EnableLinkOnceODROutlining(
     "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;
 
 /// A node in a suffix tree which represents a substring or suffix.
 ///
 /// Each node has either no children or at least two children, with the root
 /// being a exception in the empty tree.
 ///
void convertToUnsignedVec(MachineBasicBlock &MBB,
                             const TargetInstrInfo &TII) {
     unsigned Flags = TII.getMachineOutlinerMBBFlags(MBB);
 
     for (MachineBasicBlock::iterator It = MBB.begin(), Et = MBB.end(); It != Et;
          It++) {
 
       // 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;
       }
     }
 
     // After we're done every insertion, uniquely terminate this part of the
     // "string". This makes sure we won't match across basic block or function
     // boundaries since the "end" is encoded uniquely and thus appears in no
     // repeated substring.
struct MachineOutliner : public ModulePass {
   void pruneOverlaps(std::vector<std::shared_ptr<Candidate>> &CandidateList,
                      std::vector<OutlinedFunction> &FunctionList,
                      InstructionMapper &Mapper, unsigned MaxCandidateLen,
                      const TargetInstrInfo &TII);
 
   /// 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() {
for (SuffixTreeNode *Leaf : ST.LeafVector) {
     // instruction lengths we need more information than this.
     if (StringLen < 2)
       continue;
 
     // If this is a beneficial class of candidate, then every one is stored in
     // 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;
 
       if (M && M->IsInTree && M->isLeaf()) {
         // Never visit this leaf again.
         M->IsInTree = false;
         unsigned StartIdx = M->SuffixIdx;
for (auto &ChildPair : Parent.Children) {
         // start1...end1 .... start2...end2
         // That is, one must either
         // * End before the other starts
         // * Start after the other ends
         if (std::all_of(CandidatesForRepeatedSeq.begin(),
                         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].
+          // 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.getOutlininingCandidateInfo(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?
     if (Benefit < 1) {
       // 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()) << ")"
           << " >= Unoutlined instruction bytes ("
           << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"
           << " (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 << ", ";
         }
 
         R << ")";
         return R;
       });
 
       // Move to the next candidate.
       continue;
     }
 
     if (StringLen > MaxLen)
       MaxLen = StringLen;
 
     // 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);
     }
 
     FunctionList.push_back(OF);
     FunctionList.back().Candidates = CandidatesForFn;
 
MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
   MachineFunction &MF = MMI.getOrCreateMachineFunction(*F);
   MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
   const TargetSubtargetInfo &STI = MF.getSubtarget();
   const TargetInstrInfo &TII = *STI.getInstrInfo();
 
   // 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.
   for (unsigned Str : OF.Sequence) {
     MachineInstr *NewMI =
         MF.CloneMachineInstr(Mapper.IntegerInstructionMap.find(Str)->second);
     NewMI->dropMemRefs();
 
     // Don't keep debug information for outlined instructions.
     NewMI->setDebugLoc(DebugLoc());
     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);
     DIFile *Unit = SP->getFile();
     Mangler Mg;
 
     // Walk over each IR function we created in the outliner and create
     // DISubprograms for each function.
MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
   MF.getRegInfo().freezeReservedRegs(MF);
   return &MF;
 }
 
 bool MachineOutliner::outline(
     Module &M, const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
     std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper) {
 
   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)
       continue;
 
     // If not, then look at its OutlinedFunction.
     OutlinedFunction &OF = FunctionList[C.FunctionIdx];
 
     // Was its OutlinedFunction made unbeneficial during pruneOverlaps?
     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();
 
       // Output a remark telling the user that an outlined function was created,
       // and explaining where it came from.
       MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
if (!OF.MF) {
       for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
 
         // Skip over things that were pruned.
         if (!OF.Candidates[i]->InCandidateList)
           continue;
 
         R << NV(
             (Twine("StartLoc") + Twine(i)).str(),
-            Mapper.InstrList[OF.Candidates[i]->getStartIdx()]->getDebugLoc());
+            OF.Candidates[i]->front()->getDebugLoc());
         if (i != e - 1)
           R << ", ";
       }
 
       R << ")";
 
       MORE.emit(R);
       FunctionsCreated++;
     }
 
     MachineFunction *MF = OF.MF;
+    MachineBasicBlock &MBB = *C.getMBB();
+    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) {
         for (MachineOperand &MOP : MI.operands()) {
           // Skip over anything that isn't a register.
           if (!MOP.isReg())
             continue;
 
           // If it's a def, add it to the call instruction.
           if (MOP.isDef())
             CallInst->addOperand(
                 MachineOperand::CreateReg(MOP.getReg(), true, /* isDef = true */
                                           true /* isImp = true */));
         }
       };
 
       // Copy over the defs in the outlined range.
       // First inst in outlined range <-- Anything that's defined in this
       // ...                           .. range has to be added as an implicit
       // Last inst in outlined range  <-- def to the call instruction.
       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.
     NumOutlined++;
   }
 
   LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
 

lib/Target/AArch64/AArch64InstrInfo.h

public:
 
   /// AArch64 supports the MachineOutliner.
   bool useMachineOutliner() const override { return true; }
   
   bool
   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
+  outliner::TargetCostInfo getOutlininingCandidateInfo(
+      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;
+                            const outliner::TargetCostInfo &TCI) const override;
   void insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF,
-                              const MachineOutlinerInfo &MInfo) const override;
+                            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;
   /// Returns true if the instruction has a shift left that can be executed
   /// more efficiently.
   bool isExynosShiftLeftFast(const MachineInstr &MI) const;
   /// Returns true if the instruction has a shift by immediate that can be
   /// executed in one cycle less.

lib/Target/AArch64/AArch64InstrInfo.cpp

std::for_each(MBB.rbegin(),
                 [&LRU](MachineInstr &MI) { LRU.stepBackward(MI); });
 
   // If the link register is available at this point, then we can safely outline
   // the region without saving/restoring LR. Otherwise, we must emit a save and
   // restore.
   return LRU.available(AArch64::LR);
 }
 
-AArch64GenInstrInfo::MachineOutlinerInfo
+outliner::TargetCostInfo
 AArch64InstrInfo::getOutlininingCandidateInfo(
-    std::vector<
-        std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
-        &RepeatedSequenceLocs) const {
+    std::vector<outliner::Candidate> &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);
       });
   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;
     NumBytesToCreateFrame = 0;
   }
 
   else if (LastInstrOpcode == AArch64::BL || LastInstrOpcode == AArch64::BLR) {
     // FIXME: Do we need to check if the code after this uses the value of LR?
     CallID = MachineOutlinerThunk;
     FrameID = MachineOutlinerThunk;
     NumBytesForCall = 4;
     NumBytesToCreateFrame = 0;
   }
 
   else if (std::all_of(RepeatedSequenceLocs.begin(), RepeatedSequenceLocs.end(),
                        DoesntNeedLRSave)) {
     CallID = MachineOutlinerNoLRSave;
     FrameID = MachineOutlinerNoLRSave;
     NumBytesForCall = 4;
     NumBytesToCreateFrame = 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.
 
   // Handle the last instruction separately. If this is a tail call, then the
   // last instruction is a call. We don't want to save + restore in this case.
   // However, it could be possible that the last instruction is a call without
   // 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(
     MachineFunction &MF, bool OutlineFromLinkOnceODRs) const {
   const Function &F = MF.getFunction();
 
   // Can F be deduplicated by the linker? If it can, don't outline from it.
std::for_each(MBB.rbegin(),
                 [&LRU](MachineInstr &MI) { LRU.accumulate(MI); });
 
   if (!LRU.available(AArch64::LR)) 
       Flags |= MachineOutlinerMBBFlags::LRUnavailableSomewhere;
 
   return Flags;
 }
 
-AArch64GenInstrInfo::MachineOutlinerInstrType
+outliner::InstrType
 AArch64InstrInfo::getOutliningType(MachineBasicBlock::iterator &MIT,
                                    unsigned Flags) const {
   MachineInstr &MI = *MIT;
   MachineBasicBlock *MBB = MI.getParent();
   MachineFunction *MF = MBB->getParent();
   AArch64FunctionInfo *FuncInfo = MF->getInfo<AArch64FunctionInfo>();
 
   // 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
   // something containing a call, we have to emit a save and restore of LR in
   // the outlined function. Currently, this always happens by saving LR to the
   // stack. Thus, if we outline, say, half the parameters for a function call
   // plus the call, then we'll break the callee's expectations for the layout
   // of the stack.
for (const MachineOperand &MOP : MI.operands()) {
         Callee = dyn_cast<Function>(MOP.getGlobal());
         break;
       }
     }
 
     // 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;
 
     // We have a function we have information about. Check it if it's something
     // can safely outline.
     MachineFunction *CalleeMF = MF->getMMI().getMachineFunction(*Callee);
 
     // We don't know what's going on with the callee at all. Don't touch it.
     if (!CalleeMF)
       return UnknownCallOutlineType;
 
     // Check if we know anything about the callee saves on the function. If we
     // don't, then don't touch it, since that implies that we haven't
     // computed anything about its stack frame yet.
     MachineFrameInfo &MFI = CalleeMF->getFrameInfo();
     if (!MFI.isCalleeSavedInfoValid() || MFI.getStackSize() > 0 ||
         MFI.getNumObjects() > 0)
       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) ||
       MI.readsRegister(AArch64::SP, &RI)) {
     // True if there is no chance that any outlined candidate from this range
     // could require stack fixups. That is, both
     // * LR is available in the range (No save/restore around call)
     // * The range doesn't include calls (No save/restore in outlined frame)
if (MI.modifiesRegister(AArch64::SP, &RI) ||
     // %xi = ADDXri %sp, n, 0. We can't safely outline these since they might
     // be paired with later SUBXris, which might *not* end up being outlined.
     // If we mess with the stack to save something, then an ADDXri messes with
     // it *after*, then we aren't going to restore the right something from
     // the stack if we don't outline the corresponding SUBXri first. ADDXris and
     // 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.
     if (MI.mayLoadOrStore()) {
       unsigned Base;  // Filled with the base regiser of MI.
       int64_t Offset; // Filled with the offset of MI.
       unsigned DummyWidth;
 
       // 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.
       int64_t MinOffset, MaxOffset; // Unscaled offsets for the instruction.
       unsigned Scale;               // The scale to multiply the offsets by.
       getMemOpInfo(MI.getOpcode(), Scale, DummyWidth, MinOffset, MaxOffset);
 
       // TODO: We should really test what happens if an instruction overflows.
       // This is tricky to test with IR tests, but when the outliner is moved
       // 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 {
   for (MachineInstr &MI : MBB) {
     unsigned Base, Width;
     int64_t Offset;
 
     // Is this a load or store with an immediate offset with SP as the base?
for (MachineInstr &MI : MBB) {
     // checked if this instruction was legal to outline.
     int64_t NewImm = (Offset + 16) / Scale;
     StackOffsetOperand.setImm(NewImm);
   }
 }
 
 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::TCRETURNdi;
     } else {
       assert(Call->getOpcode() == AArch64::BLR);
       TailOpcode = AArch64::TCRETURNri;
     }
     MachineInstr *TC = BuildMI(MF, DebugLoc(), get(TailOpcode))
                             .add(Call->getOperand(0))
                             .addImm(0);
     MBB.insert(MBB.end(), TC);
     Call->eraseFromParent();
   }
 
   // Is there a call in the outlined range?
   auto IsNonTailCall = [](MachineInstr &MI) {
     return MI.isCall() && !MI.isReturn();
   };
   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);
 
     // LR has to be a live in so that we can save it.
     MBB.addLiveIn(AArch64::LR);
 
     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
     MachineInstr *STRXpre = BuildMI(MF, DebugLoc(), get(AArch64::STRXpre))
                                 .addReg(AArch64::SP, RegState::Define)
                                 .addReg(AArch64::LR)
                                 .addReg(AArch64::SP)
                                 .addImm(-16);
MachineInstr *LDRXpost = BuildMI(MF, DebugLoc(), get(AArch64::LDRXpost))
                                  .addReg(AArch64::SP, RegState::Define)
                                  .addReg(AArch64::LR, RegState::Define)
                                  .addReg(AArch64::SP)
                                  .addImm(16);
     Et = MBB.insert(Et, LDRXpost);
   }
 
   // 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.
   MachineInstr *ret = BuildMI(MF, DebugLoc(), get(AArch64::RET))
                           .addReg(AArch64::LR, RegState::Undef);
   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.
   // Walk over the basic block and fix up all the stack accesses.
   fixupPostOutline(MBB);
 }
 
 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()))
                             .addImm(0));
     return It;
   }
 
   // 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())));
     return It;
   }
 
   // We want to return the spot where we inserted the call.
   MachineBasicBlock::iterator CallPt;

lib/Target/X86/X86InstrInfo.h

public:
   decomposeMachineOperandsTargetFlags(unsigned TF) const override;
 
   ArrayRef<std::pair<unsigned, const char *>>
   getSerializableDirectMachineOperandTargetFlags() const override;
 
   /// 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 getOutlininingCandidateInfo(
+      std::vector<outliner::Candidate> &RepeatedSequenceLocs) const override;
 
   bool isFunctionSafeToOutlineFrom(MachineFunction &MF,
                                    bool OutlineFromLinkOnceODRs) const override;
 
-  llvm::X86GenInstrInfo::MachineOutlinerInstrType
+  outliner::InstrType
   getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const override;
 
   void insertOutlinerEpilogue(MachineBasicBlock &MBB, MachineFunction &MF,
-                              const MachineOutlinerInfo &MInfo) const override;
+                            const outliner::TargetCostInfo &TCI) const override;
 
   void insertOutlinerPrologue(MachineBasicBlock &MBB, MachineFunction &MF,
-                              const MachineOutlinerInfo &MInfo) const override;
+                            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
   /// order and/or changing the instruction's opcode and/or the immediate value
   /// operand.
   ///
   /// The arguments 'CommuteOpIdx1' and 'CommuteOpIdx2' specify the operands
   /// to be commuted.

lib/Target/X86/X86InstrInfo.cpp

 /// * Call construction overhead: 1 (jump instruction)
 /// * Frame construction overhead: 0 (don't need to return)
 ///
 enum MachineOutlinerClass {
   MachineOutlinerDefault,
   MachineOutlinerTailCall
 };
 
-X86GenInstrInfo::MachineOutlinerInfo
+outliner::TargetCostInfo
 X86InstrInfo::getOutlininingCandidateInfo(
-  std::vector<
-      std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
-      &RepeatedSequenceLocs) const {
+  std::vector<outliner::Candidate> &RepeatedSequenceLocs) const {
   unsigned SequenceSize = std::accumulate(
-      RepeatedSequenceLocs[0].first, std::next(RepeatedSequenceLocs[0].second),
+      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);
 }
 
 bool X86InstrInfo::isFunctionSafeToOutlineFrom(MachineFunction &MF,
                                            bool OutlineFromLinkOnceODRs) const {
   const Function &F = MF.getFunction();
 
   // Does the function use a red zone? If it does, then we can't risk messing
bool X86InstrInfo::isFunctionSafeToOutlineFrom(MachineFunction &MF,
   // then return false.
   if (!OutlineFromLinkOnceODRs && F.hasLinkOnceODRLinkage())
       return false;
 
   // This function is viable for outlining, so return true.
   return true;
 }
 
-X86GenInstrInfo::MachineOutlinerInstrType
+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.
   //
   // FIXME: There are instructions which are being manually built without
   // explicit uses/defs so we also have to check the MCInstrDesc. We should be
   // able to remove the extra checks once those are fixed up. For example,
   // sometimes we might get something like %rax = POP64r 1. This won't be
   // caught by modifiesRegister or readsRegister even though the instruction
   // really ought to be formed so that modifiesRegister/readsRegister would
   // catch it.
   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 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.
   // Add it in.
   MachineInstr *retq = BuildMI(MF, DebugLoc(), get(X86::RETQ));
   MBB.insert(MBB.end(), retq);
 }
 
 void X86InstrInfo::insertOutlinerPrologue(MachineBasicBlock &MBB,
                                           MachineFunction &MF,
-                                          const MachineOutlinerInfo &MInfo)
+                                          const outliner::TargetCostInfo &TCI)
                                           const {}
 
 MachineBasicBlock::iterator
 X86InstrInfo::insertOutlinedCall(Module &M, MachineBasicBlock &MBB,
                                  MachineBasicBlock::iterator &It,
                                  MachineFunction &MF,
-                                 const MachineOutlinerInfo &MInfo) const {
+                                 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())));
   } else {
     // No, insert a call.
     It = MBB.insert(It,
                   BuildMI(MF, DebugLoc(), get(X86::CALL64pcrel32))
                       .addGlobalAddress(M.getNamedValue(MF.getName())));
   }
 
   return It;
 }