1 files changed, 42 insertions, 11 deletions

diff --git a/llvm/lib/CodeGen/MachineOutliner.cpp b/llvm/lib/CodeGen/MachineOutliner.cpp
index 055cef36e0a..435ece34a19 100644
--- a/llvm/lib/CodeGen/MachineOutliner.cpp
+++ b/llvm/lib/CodeGen/MachineOutliner.cpp
@@ -939,17 +939,48 @@ unsigned MachineOutliner::findCandidates(
       SuffixTreeNode *M = ChildPair.second;
 
       if (M && M->IsInTree && M->isLeaf()) {
-        // Each sequence is over [StartIt, EndIt].
-        MachineBasicBlock::iterator StartIt = Mapper.InstrList[M->SuffixIdx];
-        MachineBasicBlock::iterator EndIt =
-            Mapper.InstrList[M->SuffixIdx + StringLen - 1];
-
-        CandidatesForRepeatedSeq.emplace_back(M->SuffixIdx, StringLen,
-                                              FunctionList.size());
-        RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt));
-
         // 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));
+        }
       }
     }
 
@@ -961,8 +992,8 @@ unsigned MachineOutliner::findCandidates(
     std::vector<unsigned> Seq;
     for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++)
       Seq.push_back(ST.Str[i]);
-    OutlinedFunction OF(FunctionList.size(), Parent.OccurrenceCount, Seq,
-                        MInfo);
+    OutlinedFunction OF(FunctionList.size(), CandidatesForRepeatedSeq.size(),
+                        Seq, MInfo);
     unsigned Benefit = OF.getBenefit();
 
     // Is it better to outline this candidate than not?