[MachineOutliner] Count savings from outlining in bytes.

[efriedma]

Summary

Counting the number of instructions is both unintuitive and inaccurate. On AArch64, this only affects the generated remarks and certain rare pseudo-instructions, but it will have a bigger impact on other targets.

[paquette]

You are entirely correct. LGTM.

[efriedma]

Forgot to run the x86 regression tests... x86 doesn't implement getInstSizeInBytes(), so the changes were completely broken. Now updated to do something sane, with some FIXMEs.

llvm/trunk/include/llvm/CodeGen/TargetInstrInfo.h

public:
   }
 
   /// Returns true if the target implements the MachineOutliner.
   virtual bool useMachineOutliner() const { return false; }
 
   /// Describes the number of instructions that it will take to call and
   /// construct a frame for a given outlining candidate.
   struct MachineOutlinerInfo {
+    /// Represents the size of a sequence in bytes. (Some instructions vary
+    /// widely in size, so just counting the instructions isn't very useful.)
+    unsigned SequenceSize;
+
     /// Number of instructions to call an outlined function for this candidate.
     unsigned CallOverhead;
 
     /// Number of instructions to construct an outlined function frame
     /// for this candidate.
     unsigned FrameOverhead;
 
     /// Represents the specific instructions that must be emitted to
     /// construct a call to this candidate.
     unsigned CallConstructionID;
 
     /// Represents the specific instructions that must be emitted to
     /// construct a frame for this candidate's outlined function.
     unsigned FrameConstructionID;
 
     MachineOutlinerInfo() {}
-    MachineOutlinerInfo(unsigned CallOverhead, unsigned FrameOverhead,
-                        unsigned CallConstructionID,
+    MachineOutlinerInfo(unsigned SequenceSize, unsigned CallOverhead,
+                        unsigned FrameOverhead, unsigned CallConstructionID,
                         unsigned FrameConstructionID)
-        : CallOverhead(CallOverhead), FrameOverhead(FrameOverhead),
+        : SequenceSize(SequenceSize), CallOverhead(CallOverhead),
+          FrameOverhead(FrameOverhead),
           CallConstructionID(CallConstructionID),
           FrameConstructionID(FrameConstructionID) {}
   };
 
   /// Returns a \p MachineOutlinerInfo struct containing target-specific
   /// information for a set of outlining candidates.
   virtual MachineOutlinerInfo getOutlininingCandidateInfo(
       std::vector<

llvm/trunk/lib/CodeGen/MachineOutliner.cpp

public:
   /// Decrement the occurrence count of this OutlinedFunction and return the
   /// new count.
   unsigned decrement() {
     assert(OccurrenceCount > 0 && "Can't decrement an empty function!");
     OccurrenceCount--;
     return getOccurrenceCount();
   }
 
-  /// Return the number of instructions it would take to outline this
+  /// Return the number of bytes it would take to outline this
   /// function.
   unsigned getOutliningCost() {
-    return (OccurrenceCount * MInfo.CallOverhead) + Sequence.size() +
+    return (OccurrenceCount * MInfo.CallOverhead) + MInfo.SequenceSize +
            MInfo.FrameOverhead;
   }
 
+  /// Return the size in bytes of the unoutlined sequences.
+  unsigned getNotOutlinedCost() {
+    return OccurrenceCount * MInfo.SequenceSize;
+  }
+
   /// Return the number of instructions that would be saved by outlining
   /// this function.
   unsigned getBenefit() {
-    unsigned NotOutlinedCost = OccurrenceCount * Sequence.size();
+    unsigned NotOutlinedCost = getNotOutlinedCost();
     unsigned OutlinedCost = getOutliningCost();
     return (NotOutlinedCost < OutlinedCost) ? 0
                                             : NotOutlinedCost - OutlinedCost;
   }
 
   OutlinedFunction(unsigned Name, unsigned OccurrenceCount,
                    const std::vector<unsigned> &Sequence,
                    TargetInstrInfo::MachineOutlinerInfo &MInfo)
if (Benefit < 1) {
           *(C.first->getParent()->getParent()), nullptr);
       MORE.emit([&]() {
         MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
                                           C.first->getDebugLoc(),
                                           C.first->getParent());
         R << "Did not outline " << NV("Length", StringLen) << " instructions"
           << " from " << NV("NumOccurrences", RepeatedSequenceLocs.size())
           << " locations."
-          << " Instructions from outlining all occurrences ("
+          << " Bytes from outlining all occurrences ("
           << NV("OutliningCost", OF.getOutliningCost()) << ")"
-          << " >= Unoutlined instruction count ("
-          << NV("NotOutliningCost", StringLen * OF.getOccurrenceCount()) << ")"
+          << " >= Unoutlined instruction bytes ("
+          << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"
           << " (Also found at: ";
 
         // Tell the user the other places the candidate was found.
         for (unsigned i = 1, e = RepeatedSequenceLocs.size(); i < e; i++) {
           R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
                   RepeatedSequenceLocs[i].first->getDebugLoc());
           if (i != e - 1)
             R << ", ";
if (!OF.MF) {
       MachineBasicBlock *MBB = &*OF.MF->begin();
 
       // Output a remark telling the user that an outlined function was created,
       // and explaining where it came from.
       MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
       MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
                                   MBB->findDebugLoc(MBB->begin()), MBB);
       R << "Saved " << NV("OutliningBenefit", OF.getBenefit())
-        << " instructions by "
+        << " bytes by "
         << "outlining " << NV("Length", OF.Sequence.size()) << " instructions "
         << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
         << " locations. "
         << "(Found at: ";
 
       // Tell the user the other places the candidate was found.
       for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
 

llvm/trunk/lib/Target/AArch64/AArch64InstrInfo.cpp

bool AArch64InstrInfo::canOutlineWithoutLRSave(
   return LRU.available(AArch64::LR);
 }
 
 AArch64GenInstrInfo::MachineOutlinerInfo
 AArch64InstrInfo::getOutlininingCandidateInfo(
     std::vector<
         std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
         &RepeatedSequenceLocs) const {
-
+  unsigned SequenceSize = std::accumulate(
+      RepeatedSequenceLocs[0].first, std::next(RepeatedSequenceLocs[0].second),
+      0, [this](unsigned Sum, const MachineInstr &MI) {
+        return Sum + getInstSizeInBytes(MI);
+      });
   unsigned CallID = MachineOutlinerDefault;
   unsigned FrameID = MachineOutlinerDefault;
-  unsigned NumInstrsForCall = 3;
-  unsigned NumInstrsToCreateFrame = 1;
+  unsigned NumBytesForCall = 12;
+  unsigned NumBytesToCreateFrame = 4;
 
   auto DoesntNeedLRSave =
       [this](std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>
                  &I) { return canOutlineWithoutLRSave(I.second); };
 
   // If the last instruction in any candidate is a terminator, then we should
   // tail call all of the candidates.
   if (RepeatedSequenceLocs[0].second->isTerminator()) {
     CallID = MachineOutlinerTailCall;
     FrameID = MachineOutlinerTailCall;
-    NumInstrsForCall = 1;
-    NumInstrsToCreateFrame = 0;
+    NumBytesForCall = 4;
+    NumBytesToCreateFrame = 0;
   }
 
   else if (std::all_of(RepeatedSequenceLocs.begin(), RepeatedSequenceLocs.end(),
                        DoesntNeedLRSave)) {
     CallID = MachineOutlinerNoLRSave;
     FrameID = MachineOutlinerNoLRSave;
-    NumInstrsForCall = 1;
-    NumInstrsToCreateFrame = 1;
+    NumBytesForCall = 4;
+    NumBytesToCreateFrame = 4;
   }
 
   // Check if the range contains a call. These require a save + restore of the
   // link register.
   if (std::any_of(RepeatedSequenceLocs[0].first, RepeatedSequenceLocs[0].second,
                   [](const MachineInstr &MI) { return MI.isCall(); }))
-    NumInstrsToCreateFrame += 2; // Save + restore the link register.
+    NumBytesToCreateFrame += 8; // Save + restore the link register.
 
   // Handle the last instruction separately. If this is a tail call, then the
   // last instruction is a call. We don't want to save + restore in this case.
   // However, it could be possible that the last instruction is a call without
   // it being valid to tail call this sequence. We should consider this as well.
   else if (RepeatedSequenceLocs[0].second->isCall() &&
            FrameID != MachineOutlinerTailCall)
-    NumInstrsToCreateFrame += 2;
+    NumBytesToCreateFrame += 8;
 
-  return MachineOutlinerInfo(NumInstrsForCall, NumInstrsToCreateFrame, CallID,
-                             FrameID);
+  return MachineOutlinerInfo(SequenceSize, NumBytesForCall,
+                             NumBytesToCreateFrame, CallID, FrameID);
 }
 
 bool AArch64InstrInfo::isFunctionSafeToOutlineFrom(
     MachineFunction &MF, bool OutlineFromLinkOnceODRs) const {
   const Function &F = MF.getFunction();
 
   // Can F be deduplicated by the linker? If it can, don't outline from it.
   if (!OutlineFromLinkOnceODRs && F.hasLinkOnceODRLinkage())

llvm/trunk/lib/Target/X86/X86InstrInfo.cpp

enum MachineOutlinerClass {
   MachineOutlinerTailCall
 };
 
 X86GenInstrInfo::MachineOutlinerInfo
 X86InstrInfo::getOutlininingCandidateInfo(
   std::vector<
       std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
       &RepeatedSequenceLocs) const {
+  unsigned SequenceSize = std::accumulate(
+      RepeatedSequenceLocs[0].first, std::next(RepeatedSequenceLocs[0].second),
+      0, [this](unsigned Sum, const MachineInstr &MI) {
+        // FIXME: x86 doesn't implement getInstSizeInBytes, so we can't
+        // tell the cost.  Just assume each instruction is one byte.
+        if (MI.isDebugInstr() || MI.isKill())
+          return Sum;
+        return Sum + 1;
+      });
 
+  // FIXME: Use real size in bytes for call and ret instructions.
   if (RepeatedSequenceLocs[0].second->isTerminator())
-    return MachineOutlinerInfo(1, // Number of instructions to emit call.
-                               0, // Number of instructions to emit frame.
+    return MachineOutlinerInfo(SequenceSize,
+                               1, // Number of bytes to emit call.
+                               0, // Number of bytes to emit frame.
                                MachineOutlinerTailCall, // Type of call.
                                MachineOutlinerTailCall // Type of frame.
                               );
 
-  return MachineOutlinerInfo(1, 1, MachineOutlinerDefault,
+  return MachineOutlinerInfo(SequenceSize, 1, 1, MachineOutlinerDefault,
                              MachineOutlinerDefault);
 }
 
 bool X86InstrInfo::isFunctionSafeToOutlineFrom(MachineFunction &MF,
                                            bool OutlineFromLinkOnceODRs) const {
   const Function &F = MF.getFunction();
 
   // Does the function use a red zone? If it does, then we can't risk messing

llvm/trunk/test/CodeGen/AArch64/machine-outliner-remarks.ll

 ; RUN: llc %s -enable-machine-outliner -mtriple=aarch64-unknown-unknown -pass-remarks=machine-outliner -pass-remarks-missed=machine-outliner -o /dev/null 2>&1 | FileCheck %s
 ; CHECK: machine-outliner-remarks.ll:5:9:
 ; CHECK-SAME: Did not outline 2 instructions from 2 locations.
-; CHECK-SAME: Instructions from outlining all occurrences (9) >=
-; CHECK-SAME: Unoutlined instruction count (4)
+; CHECK-SAME: Bytes from outlining all occurrences (36) >=
+; CHECK-SAME: Unoutlined instruction bytes (16)
 ; CHECK-SAME: (Also found at: machine-outliner-remarks.ll:13:9)
-; CHECK: remark: <unknown>:0:0: Saved 5 instructions by outlining 12 instructions
+; CHECK: remark: <unknown>:0:0: Saved 20 bytes by outlining 12 instructions
 ; CHECK-SAME: from 2 locations. (Found at: machine-outliner-remarks.ll:36:1,
 ; CHECK-SAME: machine-outliner-remarks.ll:27:9)
 ; RUN: llc %s -enable-machine-outliner -mtriple=aarch64-unknown-unknown -o /dev/null -pass-remarks-missed=machine-outliner -pass-remarks-output=%t.yaml
 ; RUN: cat %t.yaml | FileCheck %s -check-prefix=YAML
 ; YAML: --- !Missed
 ; YAML-NEXT: Pass:            machine-outliner
 ; YAML-NEXT: Name:            NotOutliningCheaper
 ; YAML-NEXT: DebugLoc:        { File: machine-outliner-remarks.ll, Line: 5, Column: 9 }
 ; YAML-NEXT: Function:        dog
 ; YAML-NEXT: Args:            
 ; YAML-NEXT:   - String:          'Did not outline '
 ; YAML-NEXT:   - Length:          '2'
 ; YAML-NEXT:   - String:          ' instructions'
 ; YAML-NEXT:   - String:          ' from '
 ; YAML-NEXT:   - NumOccurrences:  '2'
 ; YAML-NEXT:   - String:          ' locations.'
-; YAML-NEXT:   - String:          ' Instructions from outlining all occurrences ('
-; YAML-NEXT:   - OutliningCost:   '9'
+; YAML-NEXT:   - String:          ' Bytes from outlining all occurrences ('
+; YAML-NEXT:   - OutliningCost:   '36'
 ; YAML-NEXT:   - String:          ')'
-; YAML-NEXT:   - String:          ' >= Unoutlined instruction count ('
-; YAML-NEXT:   - NotOutliningCost: '4'
+; YAML-NEXT:   - String:          ' >= Unoutlined instruction bytes ('
+; YAML-NEXT:   - NotOutliningCost: '16'
 ; YAML-NEXT:   - String:          ')'
 ; YAML-NEXT:   - String:          ' (Also found at: '
 ; YAML-NEXT:   - OtherStartLoc1:  'machine-outliner-remarks.ll:13:9'
 ; YAML-NEXT:     DebugLoc:        { File: machine-outliner-remarks.ll, Line: 13, Column: 9 }
 ; YAML-NEXT:   - String:          ')'
 ; YAML: --- !Passed
 ; YAML-NEXT: Pass:            machine-outliner
 ; YAML-NEXT: Name:            OutlinedFunction
 ; YAML-NEXT: Function:        OUTLINED_FUNCTION_0
 ; YAML-NEXT: Args:            
 ; YAML-NEXT:   - String:          'Saved '
-; YAML-NEXT:   - OutliningBenefit: '5'
-; YAML-NEXT:   - String:          ' instructions by '
+; YAML-NEXT:   - OutliningBenefit: '20'
+; YAML-NEXT:   - String:          ' bytes by '
 ; YAML-NEXT:   - String:          'outlining '
 ; YAML-NEXT:   - Length:          '12'
 ; YAML-NEXT:   - String:          ' instructions '
 ; YAML-NEXT:   - String:          'from '
 ; YAML-NEXT:   - NumOccurrences:  '2'
 ; YAML-NEXT:   - String:          ' locations. '
 ; YAML-NEXT:   - String:          '(Found at: '
 ; YAML-NEXT:   - StartLoc0:       'machine-outliner-remarks.ll:36:1'