[MachineOutliner] NFC: Split up getOutliningBenefit

This is some more cleanup in preparation for some actual
functional changes. This splits getOutliningBenefit into
two cost functions: getOutliningCallOverhead and
getOutliningFrameOverhead. These functions return the
number of instructions that would be required to call
a specific function and the number of instructions
that would be required to construct a frame for a
specific funtion. The actual outlining benefit logic
is moved into the outliner, which calls these functions.

The goal of refactoring getOutliningBenefit is to:

- Get us closer to getting rid of the IsTailCall flag

- Further split up "target-specific" things and
"general algorithm" things

llvm-svn: 309356

1 files changed, 62 insertions, 21 deletions

diff --git a/llvm/lib/CodeGen/MachineOutliner.cpp b/llvm/lib/CodeGen/MachineOutliner.cpp
index ff334a3a310..8df57a27e8a 100644
--- a/llvm/lib/CodeGen/MachineOutliner.cpp
+++ b/llvm/lib/CodeGen/MachineOutliner.cpp
@@ -114,7 +114,7 @@ struct OutlinedFunction {
   /// 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.
+  /// A numbefr assigned to this function which appears at the end of its name.
   size_t Name;
 
   /// The number of candidates for this OutlinedFunction.
@@ -813,11 +813,13 @@ 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,
                      std::vector<OutlinedFunction> &FunctionList,
-                     unsigned MaxCandidateLen, const TargetInstrInfo &TII);
+                     InstructionMapper &Mapper, unsigned MaxCandidateLen,
+                     const TargetInstrInfo &TII);
 
   /// Construct a suffix tree on the instructions in \p M and outline repeated
   /// strings from that tree.
@@ -859,23 +861,40 @@ MachineOutliner::findCandidates(SuffixTree &ST, const TargetInstrInfo &TII,
     if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
       continue;
 
-    // How many instructions would outlining this string save?
+    // Figure out if this candidate is beneficial.
     size_t StringLen = Leaf->ConcatLen - Leaf->size();
-    unsigned EndVal = ST.Str[Leaf->SuffixIdx + StringLen - 1];
-
-    // Determine if this is going to be tail called.
-    // FIXME: The target should decide this. The outlining pass shouldn't care
-    // about things like tail calling. It should be representation-agnostic.
-    MachineInstr *LastInstr = Mapper.IntegerInstructionMap[EndVal];
-    assert(LastInstr && "Last instruction in sequence was unmapped!");
-    bool IsTailCall = LastInstr->isTerminator();
-    unsigned Benefit =
-        TII.getOutliningBenefit(StringLen, Parent.OccurrenceCount, IsTailCall);
-
-    // If it's not beneficial, skip it.
-    if (Benefit < 1)
+    size_t CallOverhead = 0;
+    size_t FrameOverhead = 0;
+    size_t SequenceOverhead = StringLen;
+
+    // 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()) {
+        // Each sequence is over [StartIt, EndIt].
+        MachineBasicBlock::iterator StartIt = Mapper.InstrList[M->SuffixIdx];
+        MachineBasicBlock::iterator EndIt =
+            Mapper.InstrList[M->SuffixIdx + StringLen - 1];
+        CallOverhead += TII.getOutliningCallOverhead(StartIt, EndIt);
+      }
+    }
+
+    // Figure out how many instructions it'll take to construct an outlined
+    // function frame for this sequence.
+    MachineBasicBlock::iterator StartIt = Mapper.InstrList[Leaf->SuffixIdx];
+    MachineBasicBlock::iterator EndIt =
+        Mapper.InstrList[Leaf->SuffixIdx + StringLen - 1];
+    FrameOverhead = TII.getOutliningFrameOverhead(StartIt, EndIt);
+
+    size_t OutliningCost = CallOverhead + FrameOverhead + SequenceOverhead;
+    size_t NotOutliningCost = SequenceOverhead * Parent.OccurrenceCount;
+
+    if (NotOutliningCost <= OutliningCost)
       continue;
 
+    size_t Benefit = NotOutliningCost - OutliningCost;
+
     if (StringLen > MaxLen)
       MaxLen = StringLen;
 
@@ -910,6 +929,7 @@ MachineOutliner::findCandidates(SuffixTree &ST, const TargetInstrInfo &TII,
 
 void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList,
                                     std::vector<OutlinedFunction> &FunctionList,
+                                    InstructionMapper &Mapper,
                                     unsigned MaxCandidateLen,
                                     const TargetInstrInfo &TII) {
   // TODO: Experiment with interval trees or other interval-checking structures
@@ -993,8 +1013,18 @@ void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList,
         assert(F2.OccurrenceCount > 0 &&
                "Can't remove OutlinedFunction with no occurrences!");
         F2.OccurrenceCount--;
-        F2.Benefit = TII.getOutliningBenefit(F2.Sequence.size(),
-                                             F2.OccurrenceCount, F2.IsTailCall);
+
+        // Remove the call overhead from the removed sequence.
+        MachineBasicBlock::iterator StartIt = Mapper.InstrList[C2.StartIdx];
+        MachineBasicBlock::iterator EndIt =
+            Mapper.InstrList[C2.StartIdx + C2.Len - 1];
+        F2.Benefit += TII.getOutliningCallOverhead(StartIt, EndIt);
+        // Add back one instance of the sequence.
+
+        if (F2.Sequence.size() > F2.Benefit)
+          F2.Benefit = 0;
+        else
+          F2.Benefit -= F2.Sequence.size();
 
         C2.InCandidateList = false;
 
@@ -1009,8 +1039,19 @@ void MachineOutliner::pruneOverlaps(std::vector<Candidate> &CandidateList,
         assert(F1.OccurrenceCount > 0 &&
                "Can't remove OutlinedFunction with no occurrences!");
         F1.OccurrenceCount--;
-        F1.Benefit = TII.getOutliningBenefit(F1.Sequence.size(),
-                                             F1.OccurrenceCount, F1.IsTailCall);
+
+        // Remove the call overhead from the removed sequence.
+        MachineBasicBlock::iterator StartIt = Mapper.InstrList[C1.StartIdx];
+        MachineBasicBlock::iterator EndIt =
+            Mapper.InstrList[C1.StartIdx + C1.Len - 1];
+        F2.Benefit += TII.getOutliningCallOverhead(StartIt, EndIt);
+
+        // Add back one instance of the sequence.
+        if (F1.Sequence.size() > F1.Benefit)
+          F1.Benefit = 0;
+        else
+          F1.Benefit -= F1.Sequence.size();
+
         C1.InCandidateList = false;
 
         DEBUG(dbgs() << "- Removed C1. \n";
@@ -1206,7 +1247,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);