[MachineOutliner] Add missed optimization remarks based off outliner cost model

[paquette]

Summary

This adds missed optimization remarks which report which (possibly viable) candidates were not outlined because they would be more expensive than not outlining them. Other remarks will come in separate patches.

In the case of a code size regression, if the project was built with the outliner, it'd be nice to know if it was a change in the outliner's behaviour that caused that regression. Having remarks will make that a lot easier, since it'll let us use things like the opt-viewer + optdiff.

[MatzeB]

Looks straightforward to me. Though maybe wait for Adam to take a look as he has more experience in the area.

[anemet]

You need a test ;)

lib/CodeGen/MachineOutliner.cpp

45

I don't think you need this.

918

This won't support hotness. Apparently we never added a ctor for MORE that would populate MBFI internally. Can you please add one?

It should take a MachineBranchProbabilityInfo in addition to MF but since that is an immutable pass you should be able to require it from here. Then something like this should do the trick in the ctor:

// First create a dominator tree.
MachineDominatorTree MDT;
MDT.getBase().recalculate(*MF);

// Generate LoopInfo from it.
MachineLoopInfo  MLI;
MLI.getBase().analyze(MDT.getBase());

// Finally calculate BFI.
MBFI.calculate(*MF, MBPI, MLI);

I am fine if you want to do this in a follow-on.

922

The SequenceID feels like debugging output. The goal here is to explain the user why an expected optimization not happening and not to help a compiler developer to debug the compiler. That belongs more to DEBUG(dbgs() <<) messages.

925

Just committed r311628 to add a ctor for NV taking unsigned long. You shouldn't need the cast here.

926

The function is already present in the remark via the MBB above.

927–931

I would write this as:

<< "Cost of outlining (" << NV("OutliningCost", OutliningCost) << ") is higher than not outlining (" << NV("NotOutliningCost", NotOutliningCost) << ")"

[paquette]

Updated patch to address @anemet's comments.

• Added a test for missed optimization remarks for the MachineOutliner.
• Changed remark output.
• Added some comments.

[paquette]

Updated again because I forgot to remove the #include "llvm/CodeGen/MachineBlockFrequencyInfo.h". Whoops.

[anemet]

Nice improvements.

lib/CodeGen/MachineOutliner.cpp

837

Unused now?

918–921

As before, you don't want to output the debugloc here since that is already the debugloc on the remark itself. This is kind of apparent in your test below but it's even more apparent if you used -pass-remarks-missed=machine-outliner. You'd have something like:

remark: machine-outliner-remarks.ll:5:9: machine-outliner-remarks.ll:5:9: Did not outline ...

You want to start at R << "Did not outline " ....

I think it would be a good idea to also run the test below with -pass-remarks-missed=machine-outline and then also match the remark as it is printed on the compiler. I think the register-spilling testcase should be doing both.

930–939

Probably nicer:

for (size_t i = 1, e = CandidateClass.size(); i < e; i++) {
  R << NV(...)
  if (i != e - 1)
     R << ", ";
}
R << ")";

932

Does this work: "StartLoc" + Twine(i)

I would call this OtherStartLoc<i> for easier differentiation form the main loc.

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

2

Just to repeat what I said above. Replase -pass-remarks with -pass-remarks-missed (since you're only interested in missed remarks on the stderr) and then check that as well.

12–19

I am not sure I actually understand diagnostics here. Shouldn't the non-outlined count (4) be the same as the number of instructions (2)?

[paquette]

lib/CodeGen/MachineOutliner.cpp

932

Twines don't seem to work because apparently there's no conversion to a StringRef? I guess that's something that we should probably add, unless I'm doing something wrong.

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

12–19

NotOutliningCost is the sum of the lengths of each candidate related to a repeated sequence of instructions. In this case, the sequence is length 2 with 2 occurrences, so we have 2 + 2 = 4.

Similarly, OutliningCost is the sum of the number of instructions taken to call a theoretical outlined function made from some sequence, plus the length of the sequence and anything else we'd have to add to create the frame for the function. In this case, we'd insert 3 instructions for each call, 2 instructions for the sequence, plus 1 for the return. So, we get 9.

Maybe this is somewhat unclear? A name like TotalOutlinedInstructionCount/TotalNotOutlinedInstructionCount might be better?

[paquette]

Updated diff to address Adam's comments again.

• Improved the overall remark output
• Cleaned up some of the remarks code
• Added checks for the actual command-line remarks to the test

[anemet]

LGTM.

lib/CodeGen/MachineOutliner.cpp

932

:(

This is how other places seem to be doing:

(Twine("StartLoc") + Twine(i)).str()

which is still probably better since it will only create a single std::string

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

12–19

Makes sense, thanks for explaining.

[paquette]

Got the twine thing @anemet suggested working so I threw it in.

Since I have a LGTM from him, I'm going to go ahead and commit this.

[MatzeB]

Looks like this was committed in r312194

lib/CodeGen/MachineOutliner.cpp

 ///
 /// For more information on the suffix tree data structure, please see
 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
 ///
 //===----------------------------------------------------------------------===//
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Twine.h"
+#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <functional>
 #include <map>
 #include <sstream>
 #include <tuple>
 #include <vector>
 
 #define DEBUG_TYPE "machine-outliner"
 
 using namespace llvm;
+using namespace ore;
 
 STATISTIC(NumOutlined, "Number of candidates outlined");
 STATISTIC(FunctionsCreated, "Number of functions created");
 
 namespace {
 
 /// \brief An individual sequence of instructions to be replaced with a call to
 /// an outlined function.
MachineOutliner::findCandidates(SuffixTree &ST, const TargetInstrInfo &TII,
                                 std::vector<Candidate> &CandidateList,
                                 std::vector<OutlinedFunction> &FunctionList) {
 
   CandidateList.clear();
   FunctionList.clear();
   size_t FnIdx = 0;
   size_t MaxLen = 0;
 
+  // Count the number of candidates we considered for outlining. Used to give
+  // remarks an identifier.
+  size_t NumCandidatesEvaluated = 0;
+
   // FIXME: Visit internal nodes instead of leaves.
   for (SuffixTreeNode *Leaf : ST.LeafVector) {
     assert(Leaf && "Leaves in LeafVector cannot be null!");
     if (!Leaf->IsInTree)
       continue;
 
     assert(Leaf->Parent && "All leaves must have parents!");
     SuffixTreeNode &Parent = *(Leaf->Parent);
 
     // If it doesn't appear enough, or we already outlined from it, skip it.
     if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
       continue;
 
     // Figure out if this candidate is beneficial.
     size_t StringLen = Leaf->ConcatLen - Leaf->size();
 
     // Too short to be beneficial; skip it.
     // FIXME: This isn't necessarily true for, say, X86. If we factor in
     // instruction lengths we need more information than this.
     if (StringLen < 2)
       continue;
 
+    // We've found something we might want to outline. Keep track of an ID for
+    // remarks.
+    NumCandidatesEvaluated++;
+
     size_t CallOverhead = 0;
     size_t SequenceOverhead = StringLen;
 
     // If this is a beneficial class of candidate, then every one is stored in
     // this vector.
     std::vector<Candidate> CandidatesForRepeatedSeq;
 
     // Used for getOutliningFrameOverhead.
for (SuffixTreeNode *Leaf : ST.LeafVector) {
 
     std::pair<size_t, unsigned> FrameOverheadPair =
         TII.getOutliningFrameOverhead(CandidateClass);
     size_t FrameOverhead = FrameOverheadPair.first;
 
     size_t OutliningCost = CallOverhead + FrameOverhead + SequenceOverhead;
     size_t NotOutliningCost = SequenceOverhead * Parent.OccurrenceCount;
 
-    if (NotOutliningCost <= OutliningCost)
+    // Is it better to outline this candidate than not?
+    if (NotOutliningCost <= OutliningCost) {
+      // Outlining this candidate would take more instructions than not
+      // outlining.
+      // Emit a remark explaining why we didn't outline this candidate.
+      std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator> C =
+          CandidateClass[0];
+      MachineOptimizationRemarkEmitter MORE(
+          *(C.first->getParent()->getParent()), nullptr);
+      MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
+                                        C.first->getDebugLoc(),
+                                        C.first->getParent());
+      R << NV("StartLoc0", C.first->getDebugLoc()) << ": Did not outline "
+        << NV("Length", StringLen)
+        << " instructions. Outlined instruction count ("
+        << NV("OutliningCost", OutliningCost) << ")"
+        << " >= unoutlined instruction count ("
+        << NV("NotOutliningCost", NotOutliningCost) << ")"
+        << " (Also found at: ";
+
+      // Tell the user the other places the candidate was found.
+      size_t i = 1;
+      for (size_t e = CandidateClass.size() - 1; i < e; i++) {
+        R << NV("StartLoc" + std::to_string(i),
+                CandidateClass[i].first->getDebugLoc())
+          << ", ";
+      }
+
+      R << NV("StartLoc" + std::to_string(i),
+              CandidateClass[i].first->getDebugLoc())
+        << ")";
+
+      MORE.emit(R);
+
+      // Move to the next candidate.
       continue;
+    }
 
     size_t Benefit = NotOutliningCost - OutliningCost;
 
     if (StringLen > MaxLen)
       MaxLen = StringLen;
 
     // At this point, the candidate class is seen as beneficial. Set their
     // benefit values and save them in the candidate list.

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

+; RUN: llc %s -enable-machine-outliner -mtriple=aarch64-unknown-unknown -o /dev/null -pass-remarks=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:   - StartLoc0:       'machine-outliner-remarks.ll:5:9'
+; YAML-NEXT:     DebugLoc:        { File: machine-outliner-remarks.ll, Line: 5, Column: 9 }
+; YAML-NEXT:   - String:          ': Did not outline '
+; YAML-NEXT:   - Length:          '2'
+; YAML-NEXT:   - String:          ' instructions. Outlined instruction count ('
+; YAML-NEXT:   - OutliningCost:   '9'
+; YAML-NEXT:   - String:          ')'
+; YAML-NEXT:   - String:          ' >= unoutlined instruction count ('
+; YAML-NEXT:   - NotOutliningCost: '4'
+; YAML-NEXT:   - String:          ')'
+; YAML-NEXT:   - String:          ' (Also found at: '
+; YAML-NEXT:   - StartLoc1:       'machine-outliner-remarks.ll:13:9'
+; YAML-NEXT:     DebugLoc:        { File: machine-outliner-remarks.ll, Line: 13, Column: 9 }
+; YAML-NEXT:   - String:          ')'
+
+define void @dog() #0 !dbg !8 {
+entry:
+  %x = alloca i32, align 4
+  %y = alloca i32, align 4
+  store i32 0, i32* %x, align 4, !dbg !11
+  store i32 1, i32* %y, align 4, !dbg !12
+  ret void, !dbg !13
+}
+
+define void @cat() #0 !dbg !14 {
+entry:
+  %x = alloca i32, align 4
+  %y = alloca i32, align 4
+  store i32 0, i32* %x, align 4, !dbg !15
+  store i32 1, i32* %y, align 4, !dbg !16
+  ret void, !dbg !17
+}
+
+attributes #0 = { noredzone nounwind ssp uwtable "no-frame-pointer-elim"="false" "target-cpu"="cyclone" }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5, !6}
+!llvm.ident = !{!7}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "machine-outliner-remarks.ll", directory: "/tmp")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{i32 7, !"PIC Level", i32 2}
+!7 = !{!""}
+!8 = distinct !DISubprogram(name: "dog", scope: !1, file: !1, line: 2, type: !9, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: false, unit: !0, variables: !2)
+!9 = !DISubroutineType(types: !10)
+!10 = !{null}
+!11 = !DILocation(line: 4, column: 9, scope: !8)
+!12 = !DILocation(line: 5, column: 9, scope: !8)
+!13 = !DILocation(line: 6, column: 1, scope: !8)
+!14 = distinct !DISubprogram(name: "cat", scope: !1, file: !1, line: 10, type: !9, isLocal: false, isDefinition: true, scopeLine: 11, flags: DIFlagPrototyped, isOptimized: false, unit: !0, variables: !2)
+!15 = !DILocation(line: 12, column: 9, scope: !14)
+!16 = !DILocation(line: 13, column: 9, scope: !14)
+!17 = !DILocation(line: 14, column: 1, scope: !14)