[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
diff --git a/llvm/lib/CodeGen/MachineOutliner.cpp b/llvm/lib/CodeGen/MachineOutliner.cpp
index ff334a3..8df57a2 100644
--- a/llvm/lib/CodeGen/MachineOutliner.cpp
+++ b/llvm/lib/CodeGen/MachineOutliner.cpp
@@ -114,7 +114,7 @@
/// 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 @@
///
/// \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 @@
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];
+ size_t CallOverhead = 0;
+ size_t FrameOverhead = 0;
+ size_t SequenceOverhead = StringLen;
- // 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);
+ // Figure out the call overhead for each instance of the sequence.
+ for (auto &ChildPair : Parent.Children) {
+ SuffixTreeNode *M = ChildPair.second;
- // If it's not beneficial, skip it.
- if (Benefit < 1)
+ 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 @@
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 @@
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 @@
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 @@
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);