vendor/llvm/llvm-trunk-r321017

1 files changed, 491 insertions, 360 deletions

diff --git a/lib/CodeGen/MachineOutliner.cpp b/lib/CodeGen/MachineOutliner.cpp
index fd6b2427891d..e4eb8802ac66 100644
--- a/lib/CodeGen/MachineOutliner.cpp
+++ b/lib/CodeGen/MachineOutliner.cpp
@@ -15,6 +15,23 @@
 /// instructions. If a sequence of instructions appears often, then it ought
 /// to be beneficial to pull out into a function.
 ///
+/// The MachineOutliner communicates with a given target using hooks defined in
+/// TargetInstrInfo.h. The target supplies the outliner with information on how
+/// a specific sequence of instructions should be outlined. This information
+/// is used to deduce the number of instructions necessary to
+///
+/// * Create an outlined function
+/// * Call that outlined function
+///
+/// Targets must implement
+///   * getOutliningCandidateInfo
+///   * insertOutlinerEpilogue
+///   * insertOutlinedCall
+///   * insertOutlinerPrologue
+///   * isFunctionSafeToOutlineFrom
+///
+/// in order to make use of the MachineOutliner.
+///
 /// This was originally presented at the 2016 LLVM Developers' Meeting in the
 /// talk "Reducing Code Size Using Outlining". For a high-level overview of
 /// how this pass works, the talk is available on YouTube at
@@ -42,19 +59,17 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Twine.h"
-#include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/CodeGen/TargetRegisterInfo.h"
+#include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetRegisterInfo.h"
-#include "llvm/Target/TargetSubtargetInfo.h"
 #include <functional>
 #include <map>
 #include <sstream>
@@ -64,6 +79,7 @@
 #define DEBUG_TYPE "machine-outliner"
 
 using namespace llvm;
+using namespace ore;
 
 STATISTIC(NumOutlined, "Number of candidates outlined");
 STATISTIC(FunctionsCreated, "Number of functions created");
@@ -73,19 +89,32 @@ namespace {
 /// \brief 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;
+
+public:
   /// Set to false if the candidate overlapped with another candidate.
   bool InCandidateList = true;
 
-  /// The start index of this \p Candidate.
-  size_t StartIdx;
+  /// \brief The index of this \p Candidate's \p OutlinedFunction in the list of
+  /// \p OutlinedFunctions.
+  unsigned FunctionIdx;
 
-  /// The number of instructions in this \p Candidate.
-  size_t Len;
+  /// Contains all target-specific information for this \p Candidate.
+  TargetInstrInfo::MachineOutlinerInfo MInfo;
 
-  /// The index of this \p Candidate's \p OutlinedFunction in the list of
-  /// \p OutlinedFunctions.
-  size_t FunctionIdx;
+  /// 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; }
 
   /// \brief The number of instructions that would be saved by outlining every
   /// candidate of this type.
@@ -96,51 +125,79 @@ struct Candidate {
   /// for some given candidate.
   unsigned Benefit = 0;
 
-  Candidate(size_t StartIdx, size_t Len, size_t FunctionIdx)
+  Candidate(unsigned StartIdx, unsigned Len, unsigned FunctionIdx)
       : StartIdx(StartIdx), Len(Len), FunctionIdx(FunctionIdx) {}
 
   Candidate() {}
 
   /// \brief 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 StartIdx > RHS.StartIdx; }
+  bool operator<(const Candidate &RHS) const {
+    return getStartIdx() > RHS.getStartIdx();
+  }
 };
 
 /// \brief 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.
-  size_t Name;
-
-  /// The number of candidates for this OutlinedFunction.
-  size_t OccurrenceCount = 0;
+  unsigned Name;
 
   /// \brief The sequence of integers corresponding to the instructions in this
   /// function.
   std::vector<unsigned> Sequence;
 
-  /// The number of instructions this function would save.
-  unsigned Benefit = 0;
+  /// Contains all target-specific information for this \p OutlinedFunction.
+  TargetInstrInfo::MachineOutlinerInfo MInfo;
+
+  /// 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();
+  }
+
+  /// \brief Return the number of instructions it would take to outline this
+  /// function.
+  unsigned getOutliningCost() {
+    return (OccurrenceCount * MInfo.CallOverhead) + Sequence.size() +
+           MInfo.FrameOverhead;
+  }
 
-  /// \brief Set to true if candidates for this outlined function should be
-  /// replaced with tail calls to this OutlinedFunction.
-  bool IsTailCall = false;
+  /// \brief Return the number of instructions that would be saved by outlining
+  /// this function.
+  unsigned getBenefit() {
+    unsigned NotOutlinedCost = OccurrenceCount * Sequence.size();
+    unsigned OutlinedCost = getOutliningCost();
+    return (NotOutlinedCost < OutlinedCost) ? 0
+                                            : NotOutlinedCost - OutlinedCost;
+  }
 
-  OutlinedFunction(size_t Name, size_t OccurrenceCount,
+  OutlinedFunction(unsigned Name, unsigned OccurrenceCount,
                    const std::vector<unsigned> &Sequence,
-                   unsigned Benefit, bool IsTailCall)
-      : Name(Name), OccurrenceCount(OccurrenceCount), Sequence(Sequence),
-        Benefit(Benefit), IsTailCall(IsTailCall)
-        {}
+                   TargetInstrInfo::MachineOutlinerInfo &MInfo)
+      : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence),
+        MInfo(MInfo) {}
 };
 
 /// Represents an undefined index in the suffix tree.
-const size_t EmptyIdx = -1;
+const unsigned EmptyIdx = -1;
 
 /// A node in a suffix tree which represents a substring or suffix.
 ///
@@ -170,7 +227,7 @@ struct SuffixTreeNode {
   bool IsInTree = true;
 
   /// The start index of this node's substring in the main string.
-  size_t StartIdx = EmptyIdx;
+  unsigned StartIdx = EmptyIdx;
 
   /// The end index of this node's substring in the main string.
   ///
@@ -178,24 +235,23 @@ struct SuffixTreeNode {
   /// step in the construction algorithm. To avoid having to update O(N)
   /// nodes individually at the end of every step, the end index is stored
   /// as a pointer.
-  size_t *EndIdx = nullptr;
+  unsigned *EndIdx = nullptr;
 
   /// For leaves, the start index of the suffix represented by this node.
   ///
   /// For all other nodes, this is ignored.
-  size_t SuffixIdx = EmptyIdx;
+  unsigned SuffixIdx = EmptyIdx;
 
   /// \brief For internal nodes, a pointer to the internal node representing
   /// the same sequence with the first character chopped off.
   ///
-  /// This has two major purposes in the suffix tree. The first is as a
-  /// shortcut in Ukkonen's construction algorithm. One of the things that
+  /// This acts as a shortcut in Ukkonen's algorithm. One of the things that
   /// Ukkonen's algorithm does to achieve linear-time construction is
   /// keep track of which node the next insert should be at. This makes each
   /// insert O(1), and there are a total of O(N) inserts. The suffix link
   /// helps with inserting children of internal nodes.
   ///
-  /// Say we add a child to an internal node with associated mapping S. The 
+  /// Say we add a child to an internal node with associated mapping S. The
   /// next insertion must be at the node representing S - its first character.
   /// This is given by the way that we iteratively build the tree in Ukkonen's
   /// algorithm. The main idea is to look at the suffixes of each prefix in the
@@ -204,27 +260,6 @@ struct SuffixTreeNode {
   /// move to the next insertion point in O(1) time. If we don't, then we'd
   /// have to query from the root, which takes O(N) time. This would make the
   /// construction algorithm O(N^2) rather than O(N).
-  ///
-  /// The suffix link is also used during the tree pruning process to let us
-  /// quickly throw out a bunch of potential overlaps. Say we have a sequence
-  /// S we want to outline. Then each of its suffixes contribute to at least
-  /// one overlapping case. Therefore, we can follow the suffix links
-  /// starting at the node associated with S to the root and "delete" those
-  /// nodes, save for the root. For each candidate, this removes
-  /// O(|candidate|) overlaps from the search space. We don't actually
-  /// completely invalidate these nodes though; doing that is far too
-  /// aggressive. Consider the following pathological string:
-  ///
-  /// 1 2 3 1 2 3 2 3 2 3 2 3 2 3 2 3 2 3
-  ///
-  /// If we, for the sake of example, outlined 1 2 3, then we would throw
-  /// out all instances of 2 3. This isn't desirable. To get around this,
-  /// when we visit a link node, we decrement its occurrence count by the
-  /// number of sequences we outlined in the current step. In the pathological
-  /// example, the 2 3 node would have an occurrence count of 8, while the
-  /// 1 2 3 node would have an occurrence count of 2. Thus, the 2 3 node
-  /// would survive to the next round allowing us to outline the extra
-  /// instances of 2 3.
   SuffixTreeNode *Link = nullptr;
 
   /// The parent of this node. Every node except for the root has a parent.
@@ -234,11 +269,11 @@ struct SuffixTreeNode {
   ///
   /// This is equal to the number of leaf children of the string. It represents
   /// the number of suffixes that the node's string is a prefix of.
-  size_t OccurrenceCount = 0;
+  unsigned OccurrenceCount = 0;
 
   /// The length of the string formed by concatenating the edge labels from the
   /// root to this node.
-  size_t ConcatLen = 0;
+  unsigned ConcatLen = 0;
 
   /// Returns true if this node is a leaf.
   bool isLeaf() const { return SuffixIdx != EmptyIdx; }
@@ -260,7 +295,7 @@ struct SuffixTreeNode {
     return *EndIdx - StartIdx + 1;
   }
 
-  SuffixTreeNode(size_t StartIdx, size_t *EndIdx, SuffixTreeNode *Link,
+  SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link,
                  SuffixTreeNode *Parent)
       : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link), Parent(Parent) {}
 
@@ -290,10 +325,16 @@ struct SuffixTreeNode {
 ///
 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
 class SuffixTree {
-private:
+public:
+  /// Stores each leaf node in the tree.
+  ///
+  /// This is used for finding outlining candidates.
+  std::vector<SuffixTreeNode *> LeafVector;
+
   /// Each element is an integer representing an instruction in the module.
   ArrayRef<unsigned> Str;
 
+private:
   /// Maintains each node in the tree.
   SpecificBumpPtrAllocator<SuffixTreeNode> NodeAllocator;
 
@@ -303,11 +344,6 @@ private:
   /// \p NodeAllocator like every other node in the tree.
   SuffixTreeNode *Root = nullptr;
 
-  /// Stores each leaf node in the tree.
-  ///
-  /// This is used for finding outlining candidates.
-  std::vector<SuffixTreeNode *> LeafVector;
-
   /// Maintains the end indices of the internal nodes in the tree.
   ///
   /// Each internal node is guaranteed to never have its end index change
@@ -318,7 +354,7 @@ private:
   BumpPtrAllocator InternalEndIdxAllocator;
 
   /// The end index of each leaf in the tree.
-  size_t LeafEndIdx = -1;
+  unsigned LeafEndIdx = -1;
 
   /// \brief Helper struct which keeps track of the next insertion point in
   /// Ukkonen's algorithm.
@@ -327,10 +363,10 @@ private:
     SuffixTreeNode *Node;
 
     /// The index of the first character in the substring currently being added.
-    size_t Idx = EmptyIdx;
+    unsigned Idx = EmptyIdx;
 
     /// The length of the substring we have to add at the current step.
-    size_t Len = 0;
+    unsigned Len = 0;
   };
 
   /// \brief The point the next insertion will take place at in the
@@ -344,15 +380,13 @@ private:
   /// \param Edge The label on the edge leaving \p Parent to this node.
   ///
   /// \returns A pointer to the allocated leaf node.
-  SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, size_t StartIdx,
+  SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, unsigned StartIdx,
                              unsigned Edge) {
 
     assert(StartIdx <= LeafEndIdx && "String can't start after it ends!");
 
-    SuffixTreeNode *N = new (NodeAllocator.Allocate()) SuffixTreeNode(StartIdx, 
-                                                                   &LeafEndIdx,
-                                                                       nullptr,
-                                                                      &Parent);
+    SuffixTreeNode *N = new (NodeAllocator.Allocate())
+        SuffixTreeNode(StartIdx, &LeafEndIdx, nullptr, &Parent);
     Parent.Children[Edge] = N;
 
     return N;
@@ -366,18 +400,16 @@ private:
   /// \param Edge The label on the edge leaving \p Parent to this node.
   ///
   /// \returns A pointer to the allocated internal node.
-  SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, size_t StartIdx,
-                                     size_t EndIdx, unsigned Edge) {
+  SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, unsigned StartIdx,
+                                     unsigned EndIdx, unsigned Edge) {
 
     assert(StartIdx <= EndIdx && "String can't start after it ends!");
     assert(!(!Parent && StartIdx != EmptyIdx) &&
-    "Non-root internal nodes must have parents!");
+           "Non-root internal nodes must have parents!");
 
-    size_t *E = new (InternalEndIdxAllocator) size_t(EndIdx);
-    SuffixTreeNode *N = new (NodeAllocator.Allocate()) SuffixTreeNode(StartIdx,
-                                                                      E,
-                                                                      Root,
-                                                                      Parent);
+    unsigned *E = new (InternalEndIdxAllocator) unsigned(EndIdx);
+    SuffixTreeNode *N = new (NodeAllocator.Allocate())
+        SuffixTreeNode(StartIdx, E, Root, Parent);
     if (Parent)
       Parent->Children[Edge] = N;
 
@@ -390,7 +422,7 @@ private:
   ///
   /// \param[in] CurrNode The node currently being visited.
   /// \param CurrIdx The current index of the string being visited.
-  void setSuffixIndices(SuffixTreeNode &CurrNode, size_t CurrIdx) {
+  void setSuffixIndices(SuffixTreeNode &CurrNode, unsigned CurrIdx) {
 
     bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot();
 
@@ -401,14 +433,13 @@ private:
         CurrNode.ConcatLen = CurrNode.size();
 
       if (CurrNode.Parent)
-       CurrNode.ConcatLen += CurrNode.Parent->ConcatLen;
+        CurrNode.ConcatLen += CurrNode.Parent->ConcatLen;
     }
 
     // Traverse the tree depth-first.
     for (auto &ChildPair : CurrNode.Children) {
       assert(ChildPair.second && "Node had a null child!");
-      setSuffixIndices(*ChildPair.second,
-                       CurrIdx + ChildPair.second->size());
+      setSuffixIndices(*ChildPair.second, CurrIdx + ChildPair.second->size());
     }
 
     // Is this node a leaf?
@@ -437,11 +468,11 @@ private:
   ///
   /// \returns The number of suffixes that have not been added at the end of
   /// this step.
-  unsigned extend(size_t EndIdx, size_t SuffixesToAdd) {
+  unsigned extend(unsigned EndIdx, unsigned SuffixesToAdd) {
     SuffixTreeNode *NeedsLink = nullptr;
 
     while (SuffixesToAdd > 0) {
-    
+
       // Are we waiting to add anything other than just the last character?
       if (Active.Len == 0) {
         // If not, then say the active index is the end index.
@@ -469,7 +500,7 @@ private:
         // insert a new node.
         SuffixTreeNode *NextNode = Active.Node->Children[FirstChar];
 
-        size_t SubstringLen = NextNode->size();
+        unsigned SubstringLen = NextNode->size();
 
         // Is the current suffix we're trying to insert longer than the size of
         // the child we want to move to?
@@ -515,10 +546,8 @@ private:
 
         // The node s from the diagram
         SuffixTreeNode *SplitNode =
-            insertInternalNode(Active.Node,
-                               NextNode->StartIdx,
-                               NextNode->StartIdx + Active.Len - 1,
-                               FirstChar);
+            insertInternalNode(Active.Node, NextNode->StartIdx,
+                               NextNode->StartIdx + Active.Len - 1, FirstChar);
 
         // Insert the new node representing the new substring into the tree as
         // a child of the split node. This is the node l from the diagram.
@@ -556,87 +585,6 @@ private:
   }
 
 public:
-
-  /// Find all repeated substrings that satisfy \p BenefitFn.
-  ///
-  /// If a substring appears at least twice, then it must be represented by
-  /// an internal node which appears in at least two suffixes. Each suffix is
-  /// represented by a leaf node. To do this, we visit each internal node in
-  /// the tree, using the leaf children of each internal node. If an internal
-  /// node represents a beneficial substring, then we use each of its leaf
-  /// children to find the locations of its substring.
-  ///
-  /// \param[out] CandidateList Filled with candidates representing each
-  /// beneficial substring.
-  /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions each
-  /// type of candidate.
-  /// \param BenefitFn The function to satisfy.
-  ///
-  /// \returns The length of the longest candidate found.
-  size_t findCandidates(std::vector<Candidate> &CandidateList,
-  std::vector<OutlinedFunction> &FunctionList,
-  const std::function<unsigned(SuffixTreeNode &, size_t, unsigned)>
-  &BenefitFn) {
-
-    CandidateList.clear();
-    FunctionList.clear();
-    size_t FnIdx = 0;
-    size_t MaxLen = 0;
-
-    for (SuffixTreeNode* Leaf : LeafVector) {
-      assert(Leaf && "Leaves in LeafVector cannot be null!");
-      if (!Leaf->IsInTree)
-        continue;
-
-      assert(Leaf->Parent && "All leaves must have parents!");
-      SuffixTreeNode &Parent = *(Leaf->Parent);
-
-      // If it doesn't appear enough, or we already outlined from it, skip it.
-      if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
-        continue;
-
-      size_t StringLen = Leaf->ConcatLen - Leaf->size();
-
-      // How many instructions would outlining this string save?
-      unsigned Benefit = BenefitFn(Parent,
-        StringLen, Str[Leaf->SuffixIdx + StringLen - 1]);
-
-      // If it's not beneficial, skip it.
-      if (Benefit < 1)
-        continue;
-
-      if (StringLen > MaxLen)
-        MaxLen = StringLen;
-
-      unsigned OccurrenceCount = 0;
-      for (auto &ChildPair : Parent.Children) {
-        SuffixTreeNode *M = ChildPair.second;
-
-        // Is it a leaf? If so, we have an occurrence of this candidate.
-        if (M && M->IsInTree && M->isLeaf()) {
-          OccurrenceCount++;
-          CandidateList.emplace_back(M->SuffixIdx, StringLen, FnIdx);
-          CandidateList.back().Benefit = Benefit;
-          M->IsInTree = false;
-        }
-      }
-
-      // Save the function for the new candidate sequence.
-      std::vector<unsigned> CandidateSequence;
-      for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++)
-        CandidateSequence.push_back(Str[i]);
-
-      FunctionList.emplace_back(FnIdx, OccurrenceCount, CandidateSequence,
-                                Benefit, false);
-
-      // Move to the next function.
-      FnIdx++;
-      Parent.IsInTree = false;
-    }
-
-    return MaxLen;
-  }
- 
   /// Construct a suffix tree from a sequence of unsigned integers.
   ///
   /// \param Str The string to construct the suffix tree for.
@@ -644,17 +592,18 @@ public:
     Root = insertInternalNode(nullptr, EmptyIdx, EmptyIdx, 0);
     Root->IsInTree = true;
     Active.Node = Root;
-    LeafVector = std::vector<SuffixTreeNode*>(Str.size());
+    LeafVector = std::vector<SuffixTreeNode *>(Str.size());
 
     // Keep track of the number of suffixes we have to add of the current
     // prefix.
-    size_t SuffixesToAdd = 0;
+    unsigned SuffixesToAdd = 0;
     Active.Node = Root;
 
     // Construct the suffix tree iteratively on each prefix of the string.
     // PfxEndIdx is the end index of the current prefix.
     // End is one past the last element in the string.
-    for (size_t PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End; PfxEndIdx++) {
+    for (unsigned PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End;
+         PfxEndIdx++) {
       SuffixesToAdd++;
       LeafEndIdx = PfxEndIdx; // Extend each of the leaves.
       SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd);
@@ -708,9 +657,9 @@ struct InstructionMapper {
     MachineInstr &MI = *It;
     bool WasInserted;
     DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
-    ResultIt;
+        ResultIt;
     std::tie(ResultIt, WasInserted) =
-    InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
+        InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
     unsigned MINumber = ResultIt->second;
 
     // There was an insertion.
@@ -725,10 +674,10 @@ struct InstructionMapper {
     if (LegalInstrNumber >= IllegalInstrNumber)
       report_fatal_error("Instruction mapping overflow!");
 
-    assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey()
-          && "Tried to assign DenseMap tombstone or empty key to instruction.");
-    assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey()
-          && "Tried to assign DenseMap tombstone or empty key to instruction.");
+    assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
+           "Tried to assign DenseMap tombstone or empty key to instruction.");
+    assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
+           "Tried to assign DenseMap tombstone or empty key to instruction.");
 
     return MINumber;
   }
@@ -748,13 +697,11 @@ struct InstructionMapper {
     assert(LegalInstrNumber < IllegalInstrNumber &&
            "Instruction mapping overflow!");
 
-    assert(IllegalInstrNumber !=
-      DenseMapInfo<unsigned>::getEmptyKey() &&
-      "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
+    assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
+           "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
 
-    assert(IllegalInstrNumber !=
-      DenseMapInfo<unsigned>::getTombstoneKey() &&
-      "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
+    assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
+           "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
 
     return MINumber;
   }
@@ -777,17 +724,17 @@ struct InstructionMapper {
          It++) {
 
       // Keep track of where this instruction is in the module.
-      switch(TII.getOutliningType(*It)) {
-        case TargetInstrInfo::MachineOutlinerInstrType::Illegal:
-          mapToIllegalUnsigned(It);
-          break;
+      switch (TII.getOutliningType(*It)) {
+      case TargetInstrInfo::MachineOutlinerInstrType::Illegal:
+        mapToIllegalUnsigned(It);
+        break;
 
-        case TargetInstrInfo::MachineOutlinerInstrType::Legal:
-          mapToLegalUnsigned(It);
-          break;
+      case TargetInstrInfo::MachineOutlinerInstrType::Legal:
+        mapToLegalUnsigned(It);
+        break;
 
-        case TargetInstrInfo::MachineOutlinerInstrType::Invisible:
-          break;
+      case TargetInstrInfo::MachineOutlinerInstrType::Invisible:
+        break;
       }
     }
 
@@ -804,9 +751,9 @@ struct InstructionMapper {
     // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
     // changed.
     assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
-                "DenseMapInfo<unsigned>'s empty key isn't -1!");
+           "DenseMapInfo<unsigned>'s empty key isn't -1!");
     assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
-                "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
+           "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
   }
 };
 
@@ -823,6 +770,10 @@ struct MachineOutliner : public ModulePass {
 
   static char ID;
 
+  /// \brief Set to true if the outliner should consider functions with
+  /// linkonceodr linkage.
+  bool OutlineFromLinkOnceODRs = false;
+
   StringRef getPassName() const override { return "Machine Outliner"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
@@ -832,10 +783,35 @@ struct MachineOutliner : public ModulePass {
     ModulePass::getAnalysisUsage(AU);
   }
 
-  MachineOutliner() : ModulePass(ID) {
+  MachineOutliner(bool OutlineFromLinkOnceODRs = false)
+      : ModulePass(ID), OutlineFromLinkOnceODRs(OutlineFromLinkOnceODRs) {
     initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
   }
 
+  /// Find all repeated substrings that satisfy the outlining cost model.
+  ///
+  /// If a substring appears at least twice, then it must be represented by
+  /// an internal node which appears in at least two suffixes. Each suffix is
+  /// represented by a leaf node. To do this, we visit each internal node in
+  /// the tree, using the leaf children of each internal node. If an internal
+  /// node represents a beneficial substring, then we use each of its leaf
+  /// children to find the locations of its substring.
+  ///
+  /// \param ST A suffix tree to query.
+  /// \param TII TargetInstrInfo for the target.
+  /// \param Mapper Contains outlining mapping information.
+  /// \param[out] CandidateList Filled with candidates representing each
+  /// beneficial substring.
+  /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions each
+  /// type of candidate.
+  ///
+  /// \returns The length of the longest candidate found.
+  unsigned
+  findCandidates(SuffixTree &ST, const TargetInstrInfo &TII,
+                 InstructionMapper &Mapper,
+                 std::vector<std::shared_ptr<Candidate>> &CandidateList,
+                 std::vector<OutlinedFunction> &FunctionList);
+
   /// \brief Replace the sequences of instructions represented by the
   /// \p Candidates in \p CandidateList with calls to \p MachineFunctions
   /// described in \p FunctionList.
@@ -844,7 +820,8 @@ struct MachineOutliner : public ModulePass {
   /// \param CandidateList A list of candidates to be outlined.
   /// \param FunctionList A list of functions to be inserted into the module.
   /// \param Mapper Contains the instruction mappings for the module.
-  bool outline(Module &M, const ArrayRef<Candidate> &CandidateList,
+  bool outline(Module &M,
+               const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
                std::vector<OutlinedFunction> &FunctionList,
                InstructionMapper &Mapper);
 
@@ -865,11 +842,15 @@ struct MachineOutliner : public ModulePass {
   /// \param TII TargetInstrInfo for the module.
   ///
   /// \returns The length of the longest candidate found. 0 if there are none.
-  unsigned buildCandidateList(std::vector<Candidate> &CandidateList,
-                              std::vector<OutlinedFunction> &FunctionList,
-                              SuffixTree &ST,
-                              InstructionMapper &Mapper,
-                              const TargetInstrInfo &TII);
+  unsigned
+  buildCandidateList(std::vector<std::shared_ptr<Candidate>> &CandidateList,
+                     std::vector<OutlinedFunction> &FunctionList,
+                     SuffixTree &ST, InstructionMapper &Mapper,
+                     const TargetInstrInfo &TII);
+
+  /// Helper function for pruneOverlaps.
+  /// Removes \p C from the candidate list, and updates its \p OutlinedFunction.
+  void prune(Candidate &C, std::vector<OutlinedFunction> &FunctionList);
 
   /// \brief Remove any overlapping candidates that weren't handled by the
   /// suffix tree's pruning method.
@@ -881,11 +862,12 @@ struct MachineOutliner : public ModulePass {
   ///
   /// \param[in,out] CandidateList A list of outlining candidates.
   /// \param[in,out] FunctionList A list of functions to be outlined.
+  /// \param Mapper Contains instruction mapping info for outlining.
   /// \param MaxCandidateLen The length of the longest candidate.
   /// \param TII TargetInstrInfo for the module.
-  void pruneOverlaps(std::vector<Candidate> &CandidateList,
+  void pruneOverlaps(std::vector<std::shared_ptr<Candidate>> &CandidateList,
                      std::vector<OutlinedFunction> &FunctionList,
-                     unsigned MaxCandidateLen,
+                     InstructionMapper &Mapper, unsigned MaxCandidateLen,
                      const TargetInstrInfo &TII);
 
   /// Construct a suffix tree on the instructions in \p M and outline repeated
@@ -898,16 +880,223 @@ struct MachineOutliner : public ModulePass {
 char MachineOutliner::ID = 0;
 
 namespace llvm {
-ModulePass *createMachineOutlinerPass() { return new MachineOutliner(); }
+ModulePass *createMachineOutlinerPass(bool OutlineFromLinkOnceODRs) {
+  return new MachineOutliner(OutlineFromLinkOnceODRs);
+}
+
+} // namespace llvm
+
+INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
+                false)
+
+unsigned MachineOutliner::findCandidates(
+    SuffixTree &ST, const TargetInstrInfo &TII, InstructionMapper &Mapper,
+    std::vector<std::shared_ptr<Candidate>> &CandidateList,
+    std::vector<OutlinedFunction> &FunctionList) {
+  CandidateList.clear();
+  FunctionList.clear();
+  unsigned MaxLen = 0;
+
+  // FIXME: Visit internal nodes instead of leaves.
+  for (SuffixTreeNode *Leaf : ST.LeafVector) {
+    assert(Leaf && "Leaves in LeafVector cannot be null!");
+    if (!Leaf->IsInTree)
+      continue;
+
+    assert(Leaf->Parent && "All leaves must have parents!");
+    SuffixTreeNode &Parent = *(Leaf->Parent);
+
+    // If it doesn't appear enough, or we already outlined from it, skip it.
+    if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
+      continue;
+
+    // Figure out if this candidate is beneficial.
+    unsigned StringLen = Leaf->ConcatLen - (unsigned)Leaf->size();
+
+    // Too short to be beneficial; skip it.
+    // FIXME: This isn't necessarily true for, say, X86. If we factor in
+    // 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;
+        unsigned EndIdx = StartIdx + StringLen - 1;
+
+        // Trick: Discard some candidates that would be incompatible with the
+        // ones we've already found for this sequence. This will save us some
+        // work in candidate selection.
+        //
+        // If two candidates overlap, then we can't outline them both. This
+        // happens when we have candidates that look like, say
+        //
+        // AA (where each "A" is an instruction).
+        //
+        // We might have some portion of the module that looks like this:
+        // 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
+        // be unbeneficial, then we ought to not bother.
+        //
+        // Note that two things DON'T overlap when they look like this:
+        // 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()); 
+                        })) {
+          // It doesn't overlap with anything, so we can outline it.
+          // Each sequence is over [StartIt, EndIt].
+          MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
+          MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
+
+          // Save the candidate and its location.
+          CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen,
+                                                FunctionList.size());
+          RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt));
+        }
+      }
+    }
+
+    // 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);
+    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);
+    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);
+      MORE.emit([&]() {
+        MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
+                                          C.first->getDebugLoc(),
+                                          C.first->getParent());
+        R << "Did not outline " << NV("Length", StringLen) << " instructions"
+          << " from " << NV("NumOccurrences", RepeatedSequenceLocs.size())
+          << " locations."
+          << " Instructions from outlining all occurrences ("
+          << NV("OutliningCost", OF.getOutliningCost()) << ")"
+          << " >= Unoutlined instruction count ("
+          << NV("NotOutliningCost", StringLen * OF.getOccurrenceCount()) << ")"
+          << " (Also found at: ";
+
+        // Tell the user the other places the candidate was found.
+        for (unsigned i = 1, e = RepeatedSequenceLocs.size(); i < e; i++) {
+          R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
+                  RepeatedSequenceLocs[i].first->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;
+      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;
+
+    // Move to the next function.
+    Parent.IsInTree = false;
+  }
+
+  return MaxLen;
+}
+
+// Remove C from the candidate space, and update its OutlinedFunction.
+void MachineOutliner::prune(Candidate &C,
+                            std::vector<OutlinedFunction> &FunctionList) {
+  // Get the OutlinedFunction associated with this Candidate.
+  OutlinedFunction &F = FunctionList[C.FunctionIdx];
+
+  // Update C's associated function's occurrence count.
+  F.decrement();
+
+  // Remove C from the CandidateList.
+  C.InCandidateList = false;
+
+  DEBUG(dbgs() << "- Removed a Candidate \n";
+        dbgs() << "--- Num fns left for candidate: " << F.getOccurrenceCount()
+               << "\n";
+        dbgs() << "--- Candidate's functions's benefit: " << F.getBenefit()
+               << "\n";);
 }
 
-INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE,
-                "Machine Function Outliner", false, false)
+void MachineOutliner::pruneOverlaps(
+    std::vector<std::shared_ptr<Candidate>> &CandidateList,
+    std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper,
+    unsigned MaxCandidateLen, const TargetInstrInfo &TII) {
+
+  // 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;
+
+    // C must be alive. Check if we should remove it.
+    if (FunctionList[C.FunctionIdx].getBenefit() < 1) {
+      prune(C, FunctionList);
+      return true;
+    }
+
+    // C is in the list, and F is still beneficial.
+    return false;
+  };
 
-void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList,
-                                    std::vector<OutlinedFunction> &FunctionList,
-                                    unsigned MaxCandidateLen,
-                                    const TargetInstrInfo &TII) {
   // TODO: Experiment with interval trees or other interval-checking structures
   // to lower the time complexity of this function.
   // TODO: Can we do better than the simple greedy choice?
@@ -915,56 +1104,35 @@ void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList,
   // This is O(MaxCandidateLen * CandidateList.size()).
   for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et;
        It++) {
-    Candidate &C1 = *It;
-    OutlinedFunction &F1 = FunctionList[C1.FunctionIdx];
+    Candidate &C1 = **It;
 
-    // If we removed this candidate, skip it.
-    if (!C1.InCandidateList)
+    // If C1 was already pruned, or its function is no longer beneficial for
+    // outlining, move to the next candidate.
+    if (ShouldSkipCandidate(C1))
       continue;
 
-    // Is it still worth it to outline C1?
-    if (F1.Benefit < 1 || F1.OccurrenceCount < 2) {
-      assert(F1.OccurrenceCount > 0 &&
-               "Can't remove OutlinedFunction with no occurrences!");
-      F1.OccurrenceCount--;
-      C1.InCandidateList = false;
-      continue;
-    }
-
     // The minimum start index of any candidate that could overlap with this
     // one.
     unsigned FarthestPossibleIdx = 0;
 
     // Either the index is 0, or it's at most MaxCandidateLen indices away.
-    if (C1.StartIdx > MaxCandidateLen)
-      FarthestPossibleIdx = C1.StartIdx - MaxCandidateLen;
+    if (C1.getStartIdx() > MaxCandidateLen)
+      FarthestPossibleIdx = C1.getStartIdx() - MaxCandidateLen;
 
     // Compare against the candidates in the list that start at at most
     // FarthestPossibleIdx indices away from C1. There are at most
     // MaxCandidateLen of these.
     for (auto Sit = It + 1; Sit != Et; Sit++) {
-      Candidate &C2 = *Sit;
-      OutlinedFunction &F2 = FunctionList[C2.FunctionIdx];
+      Candidate &C2 = **Sit;
 
       // Is this candidate too far away to overlap?
-      if (C2.StartIdx < FarthestPossibleIdx)
+      if (C2.getStartIdx() < FarthestPossibleIdx)
         break;
 
-      // Did we already remove this candidate in a previous step?
-      if (!C2.InCandidateList)
-        continue;
-
-      // Is the function beneficial to outline?
-      if (F2.OccurrenceCount < 2 || F2.Benefit < 1) {
-        // If not, remove this candidate and move to the next one.
-        assert(F2.OccurrenceCount > 0 &&
-               "Can't remove OutlinedFunction with no occurrences!");
-        F2.OccurrenceCount--;
-        C2.InCandidateList = false;
+      // If C2 was already pruned, or its function is no longer beneficial for
+      // outlining, move to the next candidate.
+      if (ShouldSkipCandidate(C2))
         continue;
-      }
-
-      size_t C2End = C2.StartIdx + C2.Len - 1;
 
       // Do C1 and C2 overlap?
       //
@@ -974,7 +1142,7 @@ void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList,
       // We sorted our candidate list so C2Start <= C1Start. We know that
       // C2End > C2Start since each candidate has length >= 2. Therefore, all we
       // have to check is C2End < C2Start to see if we overlap.
-      if (C2End < C1.StartIdx)
+      if (C2.getEndIdx() < C1.getStartIdx())
         continue;
 
       // C1 and C2 overlap.
@@ -982,118 +1150,52 @@ void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList,
       //
       // Approximate this by picking the one which would have saved us the
       // most instructions before any pruning.
-      if (C1.Benefit >= C2.Benefit) {
-
-        // C1 is better, so remove C2 and update C2's OutlinedFunction to
-        // reflect the removal.
-        assert(F2.OccurrenceCount > 0 &&
-               "Can't remove OutlinedFunction with no occurrences!");
-        F2.OccurrenceCount--;
-        F2.Benefit = TII.getOutliningBenefit(F2.Sequence.size(),
-                                             F2.OccurrenceCount,
-                                             F2.IsTailCall
-                                             );
-
-        C2.InCandidateList = false;
-
-        DEBUG (
-          dbgs() << "- Removed C2. \n";
-          dbgs() << "--- Num fns left for C2: " << F2.OccurrenceCount << "\n";
-          dbgs() << "--- C2's benefit: " << F2.Benefit << "\n";
-        );
 
-      } else {
-        // C2 is better, so remove C1 and update C1's OutlinedFunction to
-        // reflect the removal.
-        assert(F1.OccurrenceCount > 0 &&
-               "Can't remove OutlinedFunction with no occurrences!");
-        F1.OccurrenceCount--;
-        F1.Benefit = TII.getOutliningBenefit(F1.Sequence.size(),
-                                             F1.OccurrenceCount,
-                                             F1.IsTailCall
-                                             );
-        C1.InCandidateList = false;
-
-        DEBUG (
-          dbgs() << "- Removed C1. \n";
-          dbgs() << "--- Num fns left for C1: " << F1.OccurrenceCount << "\n";
-          dbgs() << "--- C1's benefit: " << F1.Benefit << "\n";
-        );
-
-        // C1 is out, so we don't have to compare it against anyone else.
+      // Is C2 a better candidate?
+      if (C2.Benefit > C1.Benefit) {
+        // Yes, so prune C1. Since C1 is dead, we don't have to compare it
+        // against anything anymore, so break.
+        prune(C1, FunctionList);
         break;
       }
+
+      // Prune C2 and move on to the next candidate.
+      prune(C2, FunctionList);
     }
   }
 }
 
-unsigned
-MachineOutliner::buildCandidateList(std::vector<Candidate> &CandidateList,
-                                    std::vector<OutlinedFunction> &FunctionList,
-                                    SuffixTree &ST,
-                                    InstructionMapper &Mapper,
-                                    const TargetInstrInfo &TII) {
+unsigned MachineOutliner::buildCandidateList(
+    std::vector<std::shared_ptr<Candidate>> &CandidateList,
+    std::vector<OutlinedFunction> &FunctionList, SuffixTree &ST,
+    InstructionMapper &Mapper, const TargetInstrInfo &TII) {
 
   std::vector<unsigned> CandidateSequence; // Current outlining candidate.
-  size_t MaxCandidateLen = 0; // Length of the longest candidate.
-
-  // Function for maximizing query in the suffix tree.
-  // This allows us to define more fine-grained types of things to outline in
-  // the target without putting target-specific info in the suffix tree.
-  auto BenefitFn = [&TII, &Mapper](const SuffixTreeNode &Curr,
-                                   size_t StringLen, unsigned EndVal) {
-
-    // The root represents the empty string.
-    if (Curr.isRoot())
-      return 0u;
-
-    // Is this long enough to outline?
-	// TODO: Let the target decide how "long" a string is in terms of the sizes
-	// of the instructions in the string. For example, if a call instruction
-	// is smaller than a one instruction string, we should outline that string.
-    if (StringLen < 2)
-      return 0u;
-
-    size_t Occurrences = Curr.OccurrenceCount;
+  unsigned MaxCandidateLen = 0;            // Length of the longest candidate.
 
-    // Anything we want to outline has to appear at least twice.
-    if (Occurrences < 2)
-      return 0u;
-
-    // Check if the last instruction in the sequence is a return.
-    MachineInstr *LastInstr =
-    Mapper.IntegerInstructionMap[EndVal];
-    assert(LastInstr && "Last instruction in sequence was unmapped!");
-
-    // The only way a terminator could be mapped as legal is if it was safe to
-    // tail call.
-    bool IsTailCall = LastInstr->isTerminator();
-    return TII.getOutliningBenefit(StringLen, Occurrences, IsTailCall);
-  };
-
-  MaxCandidateLen = ST.findCandidates(CandidateList, FunctionList, BenefitFn);
-
-  for (auto &OF : FunctionList)
-    OF.IsTailCall = Mapper.
-                    IntegerInstructionMap[OF.Sequence.back()]->isTerminator();
+  MaxCandidateLen =
+      findCandidates(ST, TII, Mapper, CandidateList, FunctionList);
 
   // Sort the candidates in decending order. This will simplify the outlining
   // process when we have to remove the candidates from the mapping by
   // allowing us to cut them out without keeping track of an offset.
-  std::stable_sort(CandidateList.begin(), CandidateList.end());
+  std::stable_sort(
+      CandidateList.begin(), CandidateList.end(),
+      [](const std::shared_ptr<Candidate> &LHS,
+         const std::shared_ptr<Candidate> &RHS) { return *LHS < *RHS; });
 
   return MaxCandidateLen;
 }
 
 MachineFunction *
 MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
-  InstructionMapper &Mapper) {
+                                        InstructionMapper &Mapper) {
 
   // Create the function name. This should be unique. For now, just hash the
   // module name and include it in the function name plus the number of this
   // function.
   std::ostringstream NameStream;
-  NameStream << "OUTLINED_FUNCTION" << "_" << OF.Name;
+  NameStream << "OUTLINED_FUNCTION_" << OF.Name;
 
   // Create the function using an IR-level function.
   LLVMContext &C = M.getContext();
@@ -1119,7 +1221,7 @@ MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
   // Insert the new function into the module.
   MF.insert(MF.begin(), &MBB);
 
-  TII.insertOutlinerPrologue(MBB, MF, OF.IsTailCall);
+  TII.insertOutlinerPrologue(MBB, MF, OF.MInfo);
 
   // Copy over the instructions for the function using the integer mappings in
   // its sequence.
@@ -1134,21 +1236,19 @@ MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
     MBB.insert(MBB.end(), NewMI);
   }
 
-  TII.insertOutlinerEpilogue(MBB, MF, OF.IsTailCall);
+  TII.insertOutlinerEpilogue(MBB, MF, OF.MInfo);
 
   return &MF;
 }
 
-bool MachineOutliner::outline(Module &M,
-                              const ArrayRef<Candidate> &CandidateList,
-                              std::vector<OutlinedFunction> &FunctionList,
-                              InstructionMapper &Mapper) {
+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 Candidate &C : CandidateList) {
-
+  for (const std::shared_ptr<Candidate> &Cptr : CandidateList) {
+    Candidate &C = *Cptr;
     // Was the candidate removed during pruneOverlaps?
     if (!C.InCandidateList)
       continue;
@@ -1157,14 +1257,15 @@ bool MachineOutliner::outline(Module &M,
     OutlinedFunction &OF = FunctionList[C.FunctionIdx];
 
     // Was its OutlinedFunction made unbeneficial during pruneOverlaps?
-    if (OF.OccurrenceCount < 2 || OF.Benefit < 1)
+    if (OF.getBenefit() < 1)
       continue;
 
     // If not, then outline it.
-    assert(C.StartIdx < Mapper.InstrList.size() && "Candidate out of bounds!");
-    MachineBasicBlock *MBB = (*Mapper.InstrList[C.StartIdx]).getParent();
-    MachineBasicBlock::iterator StartIt = Mapper.InstrList[C.StartIdx];
-    unsigned EndIdx = C.StartIdx + C.Len - 1;
+    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];
@@ -1175,6 +1276,37 @@ bool MachineOutliner::outline(Module &M,
     // 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);
+      MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
+                                  MBB->findDebugLoc(MBB->begin()), MBB);
+      R << "Saved " << NV("OutliningBenefit", OF.getBenefit())
+        << " instructions by "
+        << "outlining " << NV("Length", OF.Sequence.size()) << " instructions "
+        << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
+        << " locations. "
+        << "(Found at: ";
+
+      // Tell the user the other places the candidate was found.
+      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());
+        if (i != e - 1)
+          R << ", ";
+      }
+
+      R << ")";
+
+      MORE.emit(R);
       FunctionsCreated++;
     }
 
@@ -1183,8 +1315,8 @@ bool MachineOutliner::outline(Module &M,
     const TargetInstrInfo &TII = *STI.getInstrInfo();
 
     // Insert a call to the new function and erase the old sequence.
-    TII.insertOutlinedCall(M, *MBB, StartIt, *MF, OF.IsTailCall);
-    StartIt = Mapper.InstrList[C.StartIdx];
+    TII.insertOutlinedCall(M, *MBB, StartIt, *MF, C.MInfo);
+    StartIt = Mapper.InstrList[C.getStartIdx()];
     MBB->erase(StartIt, EndIt);
 
     OutlinedSomething = true;
@@ -1193,9 +1325,7 @@ bool MachineOutliner::outline(Module &M,
     NumOutlined++;
   }
 
-  DEBUG (
-    dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";
-  );
+  DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
 
   return OutlinedSomething;
 }
@@ -1207,8 +1337,8 @@ bool MachineOutliner::runOnModule(Module &M) {
     return false;
 
   MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
-  const TargetSubtargetInfo &STI = MMI.getOrCreateMachineFunction(*M.begin())
-                                      .getSubtarget();
+  const TargetSubtargetInfo &STI =
+      MMI.getOrCreateMachineFunction(*M.begin()).getSubtarget();
   const TargetRegisterInfo *TRI = STI.getRegisterInfo();
   const TargetInstrInfo *TII = STI.getInstrInfo();
 
@@ -1219,7 +1349,8 @@ bool MachineOutliner::runOnModule(Module &M) {
     MachineFunction &MF = MMI.getOrCreateMachineFunction(F);
 
     // Is the function empty? Safe to outline from?
-    if (F.empty() || !TII->isFunctionSafeToOutlineFrom(MF))
+    if (F.empty() ||
+        !TII->isFunctionSafeToOutlineFrom(MF, OutlineFromLinkOnceODRs))
       continue;
 
     // If it is, look at each MachineBasicBlock in the function.
@@ -1236,7 +1367,7 @@ bool MachineOutliner::runOnModule(Module &M) {
 
   // Construct a suffix tree, use it to find candidates, and then outline them.
   SuffixTree ST(Mapper.UnsignedVec);
-  std::vector<Candidate> CandidateList;
+  std::vector<std::shared_ptr<Candidate>> CandidateList;
   std::vector<OutlinedFunction> FunctionList;
 
   // Find all of the outlining candidates.
@@ -1244,7 +1375,7 @@ bool MachineOutliner::runOnModule(Module &M) {
       buildCandidateList(CandidateList, FunctionList, ST, Mapper, *TII);
 
   // Remove candidates that overlap with other candidates.
-  pruneOverlaps(CandidateList, FunctionList, MaxCandidateLen, *TII);
+  pruneOverlaps(CandidateList, FunctionList, Mapper, MaxCandidateLen, *TII);
 
   // Outline each of the candidates and return true if something was outlined.
   return outline(M, CandidateList, FunctionList, Mapper);