diff --git a/llvm/lib/CodeGen/MachineOutliner.cpp b/llvm/lib/CodeGen/MachineOutliner.cpp
index b072f5e..09dbf53 100644
--- a/llvm/lib/CodeGen/MachineOutliner.cpp
+++ b/llvm/lib/CodeGen/MachineOutliner.cpp
@@ -70,6 +70,75 @@
 
 namespace {
 
+/// \brief An individual sequence of instructions to be replaced with a call to
+/// an outlined function.
+struct Candidate {
+
+  /// Set to false if the candidate overlapped with another candidate.
+  bool InCandidateList = true;
+
+  /// The start index of this \p Candidate.
+  size_t StartIdx;
+
+  /// The number of instructions in this \p Candidate.
+  size_t Len;
+
+  /// The index of this \p Candidate's \p OutlinedFunction in the list of
+  /// \p OutlinedFunctions.
+  size_t FunctionIdx;
+
+  /// \brief 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(size_t StartIdx, size_t Len, size_t 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; }
+};
+
+/// \brief The information necessary to create an outlined function for some
+/// class of candidate.
+struct OutlinedFunction {
+
+  /// 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;
+
+  /// \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;
+
+  /// \brief Set to true if candidates for this outlined function should be
+  /// replaced with tail calls to this OutlinedFunction.
+  bool IsTailCall = false;
+
+  OutlinedFunction(size_t Name, size_t OccurrenceCount,
+                   const std::vector<unsigned> &Sequence,
+                   unsigned Benefit, bool IsTailCall)
+      : Name(Name), OccurrenceCount(OccurrenceCount), Sequence(Sequence),
+        Benefit(Benefit), IsTailCall(IsTailCall)
+        {}
+};
+
 /// Represents an undefined index in the suffix tree.
 const size_t EmptyIdx = -1;
 
@@ -167,6 +236,10 @@
   /// the number of suffixes that the node's string is a prefix of.
   size_t OccurrenceCount = 0;
 
+  /// The length of the string formed by concatenating the edge labels from the
+  /// root to this node.
+  size_t ConcatLen = 0;
+
   /// Returns true if this node is a leaf.
   bool isLeaf() const { return SuffixIdx != EmptyIdx; }
 
@@ -230,7 +303,9 @@
   /// \p NodeAllocator like every other node in the tree.
   SuffixTreeNode *Root = nullptr;
 
-  /// Stores each leaf in the tree for better pruning.
+  /// 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.
@@ -319,6 +394,16 @@
 
     bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot();
 
+    // Store the length of the concatenation of all strings from the root to
+    // this node.
+    if (!CurrNode.isRoot()) {
+      if (CurrNode.ConcatLen == 0)
+        CurrNode.ConcatLen = CurrNode.size();
+
+      if (CurrNode.Parent)
+       CurrNode.ConcatLen += CurrNode.Parent->ConcatLen;
+    }
+
     // Traverse the tree depth-first.
     for (auto &ChildPair : CurrNode.Children) {
       assert(ChildPair.second && "Node had a null child!");
@@ -470,263 +555,88 @@
     return SuffixesToAdd;
   }
 
-  /// \brief Return the start index and length of a string which maximizes a
-  /// benefit function by traversing the tree depth-first.
-  ///
-  /// Helper function for \p bestRepeatedSubstring.
-  ///
-  /// \param CurrNode The node currently being visited.
-  /// \param CurrLen Length of the current string.
-  /// \param[out] BestLen Length of the most beneficial substring.
-  /// \param[out] MaxBenefit Benefit of the most beneficial substring.
-  /// \param[out] BestStartIdx Start index of the most beneficial substring.
-  /// \param BenefitFn The function the query should return a maximum string
-  /// for.
-  void findBest(SuffixTreeNode &CurrNode, size_t CurrLen, size_t &BestLen,
-                size_t &MaxBenefit, size_t &BestStartIdx,
-                const std::function<unsigned(SuffixTreeNode &, size_t CurrLen)>
-                &BenefitFn) {
-
-    if (!CurrNode.IsInTree)
-      return;
-
-    // Can we traverse further down the tree?
-    if (!CurrNode.isLeaf()) {
-      // If yes, continue the traversal.
-      for (auto &ChildPair : CurrNode.Children) {
-        if (ChildPair.second && ChildPair.second->IsInTree)
-          findBest(*ChildPair.second, CurrLen + ChildPair.second->size(),
-                   BestLen, MaxBenefit, BestStartIdx, BenefitFn);
-      }
-    } else {
-      // We hit a leaf.
-      size_t StringLen = CurrLen - CurrNode.size();
-      unsigned Benefit = BenefitFn(CurrNode, StringLen);
-
-      // Did we do better than in the last step?
-      if (Benefit <= MaxBenefit)
-        return;
-
-      // We did better, so update the best string.
-      MaxBenefit = Benefit;
-      BestStartIdx = CurrNode.SuffixIdx;
-      BestLen = StringLen;
-    }
-  }
-
 public:
 
-  unsigned operator[](const size_t i) const {
-    return Str[i];
-  }
-
-  /// \brief Return a substring of the tree with maximum benefit if such a
-  /// substring exists.
+  /// Find all repeated substrings that satisfy \p BenefitFn.
   ///
-  /// Clears the input vector and fills it with a maximum substring or empty.
+  /// 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[in,out] Best The most beneficial substring in the tree. Empty
-  /// if it does not exist.
-  /// \param BenefitFn The function the query should return a maximum string
-  /// for.
-  void bestRepeatedSubstring(std::vector<unsigned> &Best,
-                 const std::function<unsigned(SuffixTreeNode &, size_t CurrLen)>
-                 &BenefitFn) {
-    Best.clear();
-    size_t Length = 0;   // Becomes the length of the best substring.
-    size_t Benefit = 0;  // Becomes the benefit of the best substring.
-    size_t StartIdx = 0; // Becomes the start index of the best substring.
-    findBest(*Root, 0, Length, Benefit, StartIdx, BenefitFn);
-
-    for (size_t Idx = 0; Idx < Length; Idx++)
-      Best.push_back(Str[Idx + StartIdx]);
-  }
-
-  /// Perform a depth-first search for \p QueryString on the suffix tree.
+  /// \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.
   ///
-  /// \param QueryString The string to search for.
-  /// \param CurrIdx The current index in \p QueryString that is being matched
-  /// against.
-  /// \param CurrNode The suffix tree node being searched in.
-  ///
-  /// \returns A \p SuffixTreeNode that \p QueryString appears in if such a
-  /// node exists, and \p nullptr otherwise.
-  SuffixTreeNode *findString(const std::vector<unsigned> &QueryString,
-                             size_t &CurrIdx, SuffixTreeNode *CurrNode) {
+  /// \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) {
 
-    // The search ended at a nonexistent or pruned node. Quit.
-    if (!CurrNode || !CurrNode->IsInTree)
-      return nullptr;
+    CandidateList.clear();
+    FunctionList.clear();
+    size_t FnIdx = 0;
+    size_t MaxLen = 0;
 
-    unsigned Edge = QueryString[CurrIdx]; // The edge we want to move on.
-    SuffixTreeNode *NextNode = CurrNode->Children[Edge]; // Next node in query.
+    for (SuffixTreeNode* Leaf : LeafVector) {
+      assert(Leaf && "Leaves in LeafVector cannot be null!");
+      if (!Leaf->IsInTree)
+        continue;
 
-    if (CurrNode->isRoot()) {
-      // If we're at the root we have to check if there's a child, and move to
-      // that child. Don't consume the character since \p Root represents the
-      // empty string.
-      if (NextNode && NextNode->IsInTree)
-        return findString(QueryString, CurrIdx, NextNode);
-      return nullptr;
-    }
+      assert(Leaf->Parent && "All leaves must have parents!");
+      SuffixTreeNode &Parent = *(Leaf->Parent);
 
-    size_t StrIdx = CurrNode->StartIdx;
-    size_t MaxIdx = QueryString.size();
-    bool ContinueSearching = false;
+      // If it doesn't appear enough, or we already outlined from it, skip it.
+      if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
+        continue;
 
-    // Match as far as possible into the string. If there's a mismatch, quit.
-    for (; CurrIdx < MaxIdx; CurrIdx++, StrIdx++) {
-      Edge = QueryString[CurrIdx];
+      size_t StringLen = Leaf->ConcatLen - Leaf->size();
 
-      // We matched perfectly, but still have a remainder to search.
-      if (StrIdx > *(CurrNode->EndIdx)) {
-        ContinueSearching = true;
-        break;
-      }
+      // How many instructions would outlining this string save?
+      unsigned Benefit = BenefitFn(Parent,
+        StringLen, Str[Leaf->SuffixIdx + StringLen - 1]);
 
-      if (Edge != Str[StrIdx])
-        return nullptr;
-    }
+      // If it's not beneficial, skip it.
+      if (Benefit < 1)
+        continue;
 
-    NextNode = CurrNode->Children[Edge];
+      if (StringLen > MaxLen)
+        MaxLen = StringLen;
 
-    // Move to the node which matches what we're looking for and continue
-    // searching.
-    if (ContinueSearching)
-      return findString(QueryString, CurrIdx, NextNode);
+      unsigned OccurrenceCount = 0;
+      for (auto &ChildPair : Parent.Children) {
+        SuffixTreeNode *M = ChildPair.second;
 
-    // We matched perfectly so we're done.
-    return CurrNode;
-  }
-
-  /// \brief Remove a node from a tree and all nodes representing proper
-  /// suffixes of that node's string.
-  ///
-  /// This is used in the outlining algorithm to reduce the number of
-  /// overlapping candidates
-  ///
-  /// \param N The suffix tree node to start pruning from.
-  /// \param Len The length of the string to be pruned.
-  ///
-  /// \returns True if this candidate didn't overlap with a previously chosen
-  /// candidate.
-  bool prune(SuffixTreeNode *N, size_t Len) {
-
-    bool NoOverlap = true;
-    std::vector<unsigned> IndicesToPrune;
-
-    // Look at each of N's children.
-    for (auto &ChildPair : N->Children) {
-      SuffixTreeNode *M = ChildPair.second;
-
-      // Is this a leaf child?
-      if (M && M->IsInTree && M->isLeaf()) {
-        // Save each leaf child's suffix indices and remove them from the tree.
-        IndicesToPrune.push_back(M->SuffixIdx);
-        M->IsInTree = false;
-      }
-    }
-
-    // Remove each suffix we have to prune from the tree. Each of these will be
-    // I + some offset for I in IndicesToPrune and some offset < Len.
-    unsigned Offset = 1;
-    for (unsigned CurrentSuffix = 1; CurrentSuffix < Len; CurrentSuffix++) {
-      for (unsigned I : IndicesToPrune) {
-
-        unsigned PruneIdx = I + Offset;
-
-        // Is this index actually in the string?
-        if (PruneIdx < LeafVector.size()) {
-          // If yes, we have to try and prune it.
-          // Was the current leaf already pruned by another candidate?
-          if (LeafVector[PruneIdx]->IsInTree) {
-            // If not, prune it.
-            LeafVector[PruneIdx]->IsInTree = false;
-          } else {
-            // If yes, signify that we've found an overlap, but keep pruning.
-            NoOverlap = false;
-          }
-
-          // Update the parent of the current leaf's occurrence count.
-          SuffixTreeNode *Parent = LeafVector[PruneIdx]->Parent;
-
-          // Is the parent still in the tree?
-          if (Parent->OccurrenceCount > 0) {
-            Parent->OccurrenceCount--;
-            Parent->IsInTree = (Parent->OccurrenceCount > 1);
-          }
+        // 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;
         }
       }
 
-      // Move to the next character in the string.
-      Offset++;
+      // 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;
     }
 
-    // We know we can never outline anything which starts one index back from
-    // the indices we want to outline. This is because our minimum outlining
-    // length is always 2.
-    for (unsigned I : IndicesToPrune) {
-      if (I > 0) {
-
-        unsigned PruneIdx = I-1;
-        SuffixTreeNode *Parent = LeafVector[PruneIdx]->Parent;
-
-        // Was the leaf one index back from I already pruned?
-        if (LeafVector[PruneIdx]->IsInTree) {
-          // If not, prune it.
-          LeafVector[PruneIdx]->IsInTree = false;
-        } else {
-          // If yes, signify that we've found an overlap, but keep pruning.
-          NoOverlap = false;
-        }
-
-        // Update the parent of the current leaf's occurrence count.
-        if (Parent->OccurrenceCount > 0) {
-          Parent->OccurrenceCount--;
-          Parent->IsInTree = (Parent->OccurrenceCount > 1);
-        }
-      }
-    }
-
-    // Finally, remove N from the tree and set its occurrence count to 0.
-    N->IsInTree = false;
-    N->OccurrenceCount = 0;
-
-    return NoOverlap;
+    return MaxLen;
   }
-
-  /// \brief Find each occurrence of of a string in \p QueryString and prune
-  /// their nodes.
-  ///
-  /// \param QueryString The string to search for.
-  /// \param[out] Occurrences The start indices of each occurrence.
-  ///
-  /// \returns Whether or not the occurrence overlaps with a previous candidate.
-  bool findOccurrencesAndPrune(const std::vector<unsigned> &QueryString,
-                               std::vector<size_t> &Occurrences) {
-    size_t Dummy = 0;
-    SuffixTreeNode *N = findString(QueryString, Dummy, Root);
-
-    if (!N || !N->IsInTree)
-      return false;
-
-    // If this is an internal node, occurrences are the number of leaf children
-    // of the node.
-    for (auto &ChildPair : N->Children) {
-      SuffixTreeNode *M = ChildPair.second;
-
-      // Is it a leaf? If so, we have an occurrence.
-      if (M && M->IsInTree && M->isLeaf())
-        Occurrences.push_back(M->SuffixIdx);
-    }
-
-    // If we're in a leaf, then this node is the only occurrence.
-    if (N->isLeaf())
-      Occurrences.push_back(N->SuffixIdx);
-
-    return prune(N, QueryString.size());
-  }
-
+ 
   /// Construct a suffix tree from a sequence of unsigned integers.
   ///
   /// \param Str The string to construct the suffix tree for.
@@ -756,64 +666,6 @@
   }
 };
 
-/// \brief An individual sequence of instructions to be replaced with a call to
-/// an outlined function.
-struct Candidate {
-
-  /// Set to false if the candidate overlapped with another candidate.
-  bool InCandidateList = true;
-
-  /// The start index of this \p Candidate.
-  size_t StartIdx;
-
-  /// The number of instructions in this \p Candidate.
-  size_t Len;
-
-  /// The index of this \p Candidate's \p OutlinedFunction in the list of
-  /// \p OutlinedFunctions.
-  size_t FunctionIdx;
-
-  Candidate(size_t StartIdx, size_t Len, size_t 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; }
-};
-
-/// \brief The information necessary to create an outlined function for some
-/// class of candidate.
-struct OutlinedFunction {
-
-  /// 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 times that this function has appeared.
-  size_t OccurrenceCount = 0;
-
-  /// \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;
-
-  bool IsTailCall = false;
-
-  OutlinedFunction(size_t Name, size_t OccurrenceCount,
-                   const std::vector<unsigned> &Sequence,
-                   unsigned Benefit, bool IsTailCall)
-      : Name(Name), OccurrenceCount(OccurrenceCount), Sequence(Sequence),
-        Benefit(Benefit), IsTailCall(IsTailCall)
-        {}
-};
-
 /// \brief Maps \p MachineInstrs to unsigned integers and stores the mappings.
 struct InstructionMapper {
 
@@ -1056,11 +908,11 @@
                                     std::vector<OutlinedFunction> &FunctionList,
                                     unsigned MaxCandidateLen,
                                     const TargetInstrInfo &TII) {
-
-  // Check for overlaps in the range. This is O(n^2) worst case, but we can
-  // alleviate that somewhat by bounding our search space using the start
-  // index of our first candidate and the maximum distance an overlapping
-  // candidate could have from the first candidate.
+  // 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?
+  // Check for overlaps in the range.
+  // This is O(MaxCandidateLen * CandidateList.size()).
   for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et;
        It++) {
     Candidate &C1 = *It;
@@ -1070,9 +922,11 @@
     if (!C1.InCandidateList)
       continue;
 
-    // If the candidate's function isn't good to outline anymore, then
-    // remove the candidate and skip it.
-    if (F1.OccurrenceCount < 2 || F1.Benefit < 1) {
+    // 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;
     }
@@ -1085,23 +939,14 @@
     if (C1.StartIdx > MaxCandidateLen)
       FarthestPossibleIdx = C1.StartIdx - MaxCandidateLen;
 
-    // Compare against the other candidates in the list.
-    // This is at most MaxCandidateLen/2 other candidates.
-    // This is because each candidate has to be at least 2 indices away.
-    // = O(n * MaxCandidateLen/2) comparisons
-    //
-    // On average, the maximum length of a candidate is quite small; a fraction
-    // of the total module length in terms of instructions. If the maximum
-    // candidate length is large, then there are fewer possible candidates to
-    // compare against in the first place.
+    // 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];
 
       // Is this candidate too far away to overlap?
-      // NOTE: This will be true in
-      //    O(max(FarthestPossibleIdx/2, #Candidates remaining)) steps
-      // for every candidate.
       if (C2.StartIdx < FarthestPossibleIdx)
         break;
 
@@ -1112,6 +957,9 @@
       // 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;
         continue;
       }
@@ -1129,33 +977,52 @@
       if (C2End < C1.StartIdx)
         continue;
 
-      // C2 overlaps with C1. Because we pruned the tree already, the only way
-      // this can happen is if C1 is a proper suffix of C2. Thus, we must have
-      // found C1 first during our query, so it must have benefit greater or
-      // equal to C2. Greedily pick C1 as the candidate to keep and toss out C2.
-      DEBUG (
-            size_t C1End = C1.StartIdx + C1.Len - 1;
-            dbgs() << "- Found an overlap to purge.\n";
-            dbgs() << "--- C1 :[" << C1.StartIdx << ", " << C1End << "]\n";
-            dbgs() << "--- C2 :[" << C2.StartIdx << ", " << C2End << "]\n";
-            );
+      // C1 and C2 overlap.
+      // We need to choose the better of the two.
+      //
+      // Approximate this by picking the one which would have saved us the
+      // most instructions before any pruning.
+      if (C1.Benefit >= C2.Benefit) {
 
-      // Update the function's occurrence count and benefit to reflec that C2
-      // is being removed.
-      F2.OccurrenceCount--;
-      F2.Benefit = TII.getOutliningBenefit(F2.Sequence.size(),
-                                           F2.OccurrenceCount,
-                                           F2.IsTailCall
-                                           );
+        // 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
+                                             );
 
-      // Mark C2 as not in the list.
-      C2.InCandidateList = false;
+        C2.InCandidateList = false;
 
-      DEBUG (
-            dbgs() << "- Removed C2. \n";
-            dbgs() << "--- Num fns left for C2: " << F2.OccurrenceCount << "\n";
-            dbgs() << "--- C2's benefit: " << F2.Benefit << "\n";
-            );
+        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.
+        break;
+      }
     }
   }
 }
@@ -1168,98 +1035,47 @@
                                     const TargetInstrInfo &TII) {
 
   std::vector<unsigned> CandidateSequence; // Current outlining candidate.
-  unsigned MaxCandidateLen = 0; // Length of the longest 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, &ST, &Mapper](const SuffixTreeNode &Curr,
-                                        size_t StringLen) {
+                                          size_t StringLen, unsigned EndVal) {
 
-    // Any leaf whose parent is the root only has one occurrence.
-    if (Curr.Parent->isRoot())
+    // The root represents the empty string.
+    if (Curr.isRoot())
       return 0u;
 
-    // Anything with length < 2 will never be beneficial on any target.
+    // 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.Parent->OccurrenceCount;
+    size_t Occurrences = Curr.OccurrenceCount;
 
-    // Anything with fewer than 2 occurrences will never be beneficial on any
-    // target.
+    // 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[ST[Curr.SuffixIdx + StringLen - 1]];
+    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);
   };
 
-  // Repeatedly query the suffix tree for the substring that maximizes
-  // BenefitFn. Find the occurrences of that string, prune the tree, and store
-  // each occurrence as a candidate.
-  for (ST.bestRepeatedSubstring(CandidateSequence, BenefitFn);
-       CandidateSequence.size() > 1;
-       ST.bestRepeatedSubstring(CandidateSequence, BenefitFn)) {
+  MaxCandidateLen = ST.findCandidates(CandidateList, FunctionList, BenefitFn);
 
-    std::vector<size_t> Occurrences;
-
-    bool GotNonOverlappingCandidate =
-        ST.findOccurrencesAndPrune(CandidateSequence, Occurrences);
-
-    // Is the candidate we found known to overlap with something we already
-    // outlined?
-    if (!GotNonOverlappingCandidate)
-      continue;
-
-    // Is this candidate the longest so far?
-    if (CandidateSequence.size() > MaxCandidateLen)
-      MaxCandidateLen = CandidateSequence.size();
-
-    MachineInstr *LastInstr =
-    Mapper.IntegerInstructionMap[CandidateSequence.back()];
-    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();
-
-    // Keep track of the benefit of outlining this candidate in its
-    // OutlinedFunction.
-    unsigned FnBenefit = TII.getOutliningBenefit(CandidateSequence.size(),
-                                                 Occurrences.size(),
-                                                 IsTailCall
-                                                 );
-
-    assert(FnBenefit > 0 && "Function cannot be unbeneficial!");
-
-    // Save an OutlinedFunction for this candidate.
-    FunctionList.emplace_back(
-        FunctionList.size(), // Number of this function.
-        Occurrences.size(),  // Number of occurrences.
-        CandidateSequence,   // Sequence to outline.
-        FnBenefit,           // Instructions saved by outlining this function.
-        IsTailCall           // Flag set if this function is to be tail called.
-        );
-
-    // Save each of the occurrences of the candidate so we can outline them.
-    for (size_t &Occ : Occurrences)
-      CandidateList.emplace_back(
-          Occ,                      // Starting idx in that MBB.
-          CandidateSequence.size(), // Candidate length.
-          FunctionList.size() - 1   // Idx of the corresponding function.
-          );
-
-    FunctionsCreated++;
-  }
+  for (auto &OF : FunctionList)
+    OF.IsTailCall = Mapper.
+                    IntegerInstructionMap[OF.Sequence.back()]->isTerminator();
 
   // Sort the candidates in decending order. This will simplify the outlining
   // process when we have to remove the candidates from the mapping by
@@ -1357,8 +1173,10 @@
     EndIt++; // Erase needs one past the end index.
 
     // Does this candidate have a function yet?
-    if (!OF.MF)
+    if (!OF.MF) {
       OF.MF = createOutlinedFunction(M, OF, Mapper);
+      FunctionsCreated++;
+    }
 
     MachineFunction *MF = OF.MF;
     const TargetSubtargetInfo &STI = MF->getSubtarget();
@@ -1421,9 +1239,13 @@
   std::vector<Candidate> CandidateList;
   std::vector<OutlinedFunction> FunctionList;
 
+  // Find all of the outlining candidates.
   unsigned MaxCandidateLen =
       buildCandidateList(CandidateList, FunctionList, ST, Mapper, *TII);
 
+  // Remove candidates that overlap with other candidates.
   pruneOverlaps(CandidateList, FunctionList, MaxCandidateLen, *TII);
+
+  // Outline each of the candidates and return true if something was outlined.
   return outline(M, CandidateList, FunctionList, Mapper);
 }