From 55c1b415d451f34c805e617cb161497c22367b73 Mon Sep 17 00:00:00 2001 From: Jessica Paquette Date: Fri, 1 Dec 2017 21:56:56 +0000 Subject: [PATCH] [MachineOutliner] NFC: Throw out self-intersections on candidates early Currently, the outliner considers candidates that intersect with themselves in the candidate pruning step. That is, candidates of the form "AA" in ranges like "AAAAAA". In that range, it looks like there are 5 instances of "AA" that could possibly be outlined, and that's considered in the benefit calculation. However, only at most 3 instances of "AA" could ever be outlined in "AAAAAA". Thus, it's possible to pass through "AA" to the candidate selection step even though it's *never* the case that "AA" could be outlined. This makes it so that when we find candidates, we consider only non-overlapping occurrences of that candidate. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@319588 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineOutliner.cpp | 53 ++++++++++++++++++++++++++++++++--------- 1 file changed, 42 insertions(+), 11 deletions(-) diff --git a/lib/CodeGen/MachineOutliner.cpp b/lib/CodeGen/MachineOutliner.cpp index 055cef36e0a..435ece34a19 100644 --- a/lib/CodeGen/MachineOutliner.cpp +++ b/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 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? -- 2.11.0