[GreedyRA ORE] Add Cost of spill locations into remark

[skatkov]

Summary

Cost of spill location is computed basing on relative branch frequency where corresponding spill/reload/copy is located.

While the number itself is highly depends on incoming IR, the total cost can be used when do some changes in RA.

[skatkov]

rebase

[skatkov]

rebase + test update.

[reames]

LGTM w/required changes.

llvm/lib/CodeGen/RegAllocGreedy.cpp

583

Personally, I don't think this function adds any clarity since it's used once, and the naming isn't super obvious. Please just inline this into the caller w/a comment about computing cost.

3159

replace "spills location cost" with "total spill cost", analogously for the others below.

llvm/lib/CodeGen/RegAllocGreedy.cpp

private:
   /// Greedy RA statistic to remark.
   struct RAGreedyStats {
     unsigned Reloads = 0;
     unsigned FoldedReloads = 0;
     unsigned ZeroCostFoldedReloads = 0;
     unsigned Spills = 0;
     unsigned FoldedSpills = 0;
     unsigned Copies = 0;
+    float ReloadsCost = 0.0f;
+    float FoldedReloadsCost = 0.0f;
+    float SpillsCost = 0.0f;
+    float FoldedSpillsCost = 0.0f;
+    float CopiesCost = 0.0f;
 
     bool isEmpty() {
       return !(Reloads || FoldedReloads || Spills || FoldedSpills ||
                ZeroCostFoldedReloads || Copies);
     }
 
     void add(RAGreedyStats other) {
       Reloads += other.Reloads;
       FoldedReloads += other.FoldedReloads;
       ZeroCostFoldedReloads += other.ZeroCostFoldedReloads;
       Spills += other.Spills;
       FoldedSpills += other.FoldedSpills;
       Copies += other.Copies;
+      ReloadsCost += other.ReloadsCost;
+      FoldedReloadsCost += other.FoldedReloadsCost;
+      SpillsCost += other.SpillsCost;
+      FoldedSpillsCost += other.FoldedSpillsCost;
+      CopiesCost += other.CopiesCost;
+    }
+
+    void addCost(float freq) {
+      ReloadsCost += freq * Reloads;
+      FoldedReloadsCost += freq * FoldedReloads;
+      SpillsCost += freq * Spills;
+      FoldedSpillsCost += freq * FoldedSpills;
+      CopiesCost += freq * Copies;
     }
 
     void report(MachineOptimizationRemarkMissed &R);
   };
 
   /// Compute statistic for a basic block.
   RAGreedyStats computeStats(MachineBasicBlock &MBB);
 
MCRegister RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
 
   // The live virtual register requesting allocation was spilled, so tell
   // the caller not to allocate anything during this round.
   return 0;
 }
 
 void RAGreedy::RAGreedyStats::report(MachineOptimizationRemarkMissed &R) {
   using namespace ore;
-  if (Spills)
+  if (Spills) {
     R << NV("NumSpills", Spills) << " spills ";
-  if (FoldedSpills)
+    R << NV("SpillsLocationCost", SpillsCost) << " spills location cost ";
+  }
+  if (FoldedSpills) {
     R << NV("NumFoldedSpills", FoldedSpills) << " folded spills ";
-  if (Reloads)
+    R << NV("FoldedSpillsLocationCost", FoldedSpillsCost)
+      << " folded spills location cost ";
+  }
+  if (Reloads) {
     R << NV("NumReloads", Reloads) << " reloads ";
-  if (FoldedReloads)
+    R << NV("ReloadsLocationCost", ReloadsCost) << " reloads location cost ";
+  }
+  if (FoldedReloads) {
     R << NV("NumFoldedReloads", FoldedReloads) << " folded reloads ";
+    R << NV("FoldedReloadsLocationCost", FoldedReloadsCost)
+      << " folded reloads location cost ";
+  }
   if (ZeroCostFoldedReloads)
     R << NV("NumZeroCostFoldedReloads", ZeroCostFoldedReloads)
       << " zero cost folded reloads ";
-  if (Copies)
+  if (Copies) {
     R << NV("NumVRCopies", Copies) << " virtual registers copies ";
+    R << NV("CopiesLocationCost", CopiesCost) << " copies location cost ";
+  }
 }
 
 RAGreedy::RAGreedyStats RAGreedy::computeStats(MachineBasicBlock &MBB) {
   RAGreedyStats Stats;
   const MachineFrameInfo &MFI = MF->getFrameInfo();
   int FI;
 
   auto isSpillSlotAccess = [&MFI](const MachineMemOperand *A) {
if (TII->hasLoadFromStackSlot(MI, Accesses) &&
       continue;
     }
     Accesses.clear();
     if (TII->hasStoreToStackSlot(MI, Accesses) &&
         llvm::any_of(Accesses, isSpillSlotAccess)) {
       Stats.FoldedSpills += Accesses.size();
     }
   }
+  Stats.addCost(MBFI->getBlockFreqRelativeToEntryBlock(&MBB));
   return Stats;
 }
 
 RAGreedy::RAGreedyStats RAGreedy::reportStats(MachineLoop *L) {
   RAGreedyStats Stats;
 
   // Sum up the spill and reloads in subloops.
   for (MachineLoop *SubLoop : *L)

llvm/test/CodeGen/AArch64/arm64-spill-remarks-treshold-hotness.ll

 ; RUN: llc < %s -mtriple=arm64-apple-ios7.0 -aarch64-neon-syntax=apple -pass-remarks-missed=regalloc \
 ; RUN:       -pass-remarks-with-hotness 2>&1 | FileCheck %s
 
 ; RUN: llc < %s -mtriple=arm64-apple-ios7.0 -aarch64-neon-syntax=apple -pass-remarks-missed=regalloc \
 ; RUN:       -pass-remarks-with-hotness -pass-remarks-hotness-threshold=1 \
 ; RUN:       2>&1 | FileCheck -check-prefix=THRESHOLD %s
 
-; CHECK: remark: /tmp/kk.c:3:20: 1 spills 1 reloads generated in loop{{$}}
+; CHECK: remark: /tmp/kk.c:3:20: 1 spills 3.187500e+01 spills location cost 1 reloads 3.187500e+01 reloads location cost generated in loop{{$}}
 ; THRESHOLD-NOT: remark
 
 define void @fpr128(<4 x float>* %p) nounwind ssp {
 entry:
   br label %loop, !dbg !8
 
 loop:
   %i = phi i32 [ 0, %entry], [ %i.2, %end2 ]

llvm/test/CodeGen/AArch64/arm64-spill-remarks.ll

 ; RUN:       -pass-remarks-with-hotness -pass-remarks-hotness-threshold=500 \
 ; RUN:       2>&1 | FileCheck -check-prefix=NO_REMARK %s
 ; RUN: cat %t.threshold.yaml | FileCheck -check-prefix=THRESHOLD_YAML %s
 
 ; This has two nested loops, each with one value that has to be spilled and
 ; then reloaded.
 
 ; (loop3:)
-; REMARK: remark: /tmp/kk.c:3:20: 1 spills 1 reloads generated in loop{{$}}
+; REMARK: remark: /tmp/kk.c:3:20: 1 spills 1.000000e+02 spills location cost 1 reloads 1.000000e+02 reloads location cost generated in loop{{$}}
 ; (loop2:)
-; REMARK: remark: /tmp/kk.c:2:20: 1 spills 1 reloads generated in loop{{$}}
+; REMARK: remark: /tmp/kk.c:2:20: 1 spills 1.000000e+04 spills location cost 1 reloads 1.000000e+04 reloads location cost generated in loop{{$}}
 ; (loop:)
-; REMARK: remark: /tmp/kk.c:1:20: 2 spills 2 reloads generated in loop{{$}}
+; REMARK: remark: /tmp/kk.c:1:20: 2 spills 1.010000e+04 spills location cost 2 reloads 1.010000e+04 reloads location cost generated in loop{{$}}
 ; (func:)
-; REMARK: remark: /tmp/kk.c:1:1: 3 spills 3 reloads generated in function{{$}}
+; REMARK: remark: /tmp/kk.c:1:1: 3 spills 1.020000e+04 spills location cost 3 reloads 1.020000e+04 reloads location cost generated in function
 
 ; (loop3:)
-; HOTNESS: remark: /tmp/kk.c:3:20: 1 spills 1 reloads generated in loop (hotness: 300)
+; HOTNESS: remark: /tmp/kk.c:3:20: 1 spills 1.000000e+02 spills location cost 1 reloads 1.000000e+02 reloads location cost generated in loop (hotness: 300)
 ; (loop2:)
-; HOTNESS: remark: /tmp/kk.c:2:20: 1 spills 1 reloads generated in loop (hotness: 30000)
+; HOTNESS: remark: /tmp/kk.c:2:20: 1 spills 1.000000e+04 spills location cost 1 reloads 1.000000e+04 reloads location cost generated in loop (hotness: 30000)
 ; (loop:)
-; HOTNESS: remark: /tmp/kk.c:1:20: 2 spills 2 reloads generated in loop (hotness: 300)
+; HOTNESS: remark: /tmp/kk.c:1:20: 2 spills 1.010000e+04 spills location cost 2 reloads 1.010000e+04 reloads location cost generated in loop (hotness: 300)
 
 ; NO_REMARK-NOT: remark
 
 ; THRESHOLD-NOT: (hotness: 300)
-; THRESHOLD: remark: /tmp/kk.c:2:20: 1 spills 1 reloads generated in loop (hotness: 30000)
+; THRESHOLD: remark: /tmp/kk.c:2:20: 1 spills 1.000000e+04 spills location cost 1 reloads 1.000000e+04 reloads location cost generated in loop (hotness: 30000)
 
 ; YAML: --- !Missed
 ; YAML: Pass:            regalloc
 ; YAML: Name:            LoopSpillReloadCopies
 ; YAML: DebugLoc:        { File: '/tmp/kk.c', Line: 3, Column: 20 }
 ; YAML: Function:        fpr128
 ; YAML: Hotness:         300
 ; YAML: Args:
 ; YAML:   - NumSpills:       '1'
 ; YAML:   - String:          ' spills '
+; YAML:   - SpillsLocationCost: '1.000000e+02'
+; YAML:   - String:          ' spills location cost '
 ; YAML:   - NumReloads:      '1'
 ; YAML:   - String:          ' reloads '
+; YAML:   - ReloadsLocationCost: '1.000000e+02'
+; YAML:   - String:          ' reloads location cost '
 ; YAML:   - String:          generated in loop
 ; YAML: ...
 ; YAML: --- !Missed
 ; YAML: Pass:            regalloc
 ; YAML: Name:            LoopSpillReloadCopies
 ; YAML: DebugLoc:        { File: '/tmp/kk.c', Line: 2, Column: 20 }
 ; YAML: Function:        fpr128
 ; YAML: Hotness:         30000
 ; YAML: Args:
 ; YAML:   - NumSpills:       '1'
 ; YAML:   - String:          ' spills '
+; YAML:   - SpillsLocationCost: '1.000000e+04'
+; YAML:   - String:          ' spills location cost '
 ; YAML:   - NumReloads:      '1'
 ; YAML:   - String:          ' reloads '
+; YAML:   - ReloadsLocationCost: '1.000000e+04'
+; YAML:   - String:          ' reloads location cost '
 ; YAML:   - String:          generated in loop
 ; YAML: ...
 ; YAML: --- !Missed
 ; YAML: Pass:            regalloc
 ; YAML: Name:            LoopSpillReloadCopies
 ; YAML: DebugLoc:        { File: '/tmp/kk.c', Line: 1, Column: 20 }
 ; YAML: Function:        fpr128
 ; YAML: Hotness:         300
 ; YAML: Args:
 ; YAML:   - NumSpills:       '2'
 ; YAML:   - String:          ' spills '
+; YAML:   - SpillsLocationCost: '1.010000e+04'
+; YAML:   - String:          ' spills location cost '
 ; YAML:   - NumReloads:      '2'
 ; YAML:   - String:          ' reloads '
+; YAML:   - ReloadsLocationCost: '1.010000e+04'
+; YAML:   - String:          ' reloads location cost '
 ; YAML:   - String:          generated in loop
 ; YAML: ...
 ; YAML: --- !Missed
 ; YAML: Pass:            regalloc
 ; YAML: Name:            SpillReloadCopies
 ; YAML: DebugLoc:        { File: '/tmp/kk.c', Line: 1, Column: 1 }
 ; YAML: Function:        fpr128
 ; YAML: Hotness:         3
 ; YAML: Args:
 ; YAML:   - NumSpills:       '3'
 ; YAML:   - String:          ' spills '
+; YAML:   - SpillsLocationCost: '1.020000e+04'
+; YAML:   - String:          ' spills location cost '
 ; YAML:   - NumReloads:      '3'
 ; YAML:   - String:          ' reloads '
+; YAML:   - ReloadsLocationCost: '1.020000e+04'
+; YAML:   - String:          ' reloads location cost '
 ; YAML:   - String:          generated in function
 ; YAML: ...
 
 ; THRESHOLD_YAML-NOT: Hotness:         300{{$}}
 ; THRESHOLD_YAML: --- !Missed
 ; THRESHOLD_YAML: Pass:            regalloc
 ; THRESHOLD_YAML: Name:            LoopSpillReloadCopies
 ; THRESHOLD_YAML: DebugLoc:        { File: '/tmp/kk.c', Line: 2, Column: 20 }
 ; THRESHOLD_YAML: Function:        fpr128
 ; THRESHOLD_YAML: Hotness:         30000
 ; THRESHOLD_YAML: Args:
 ; THRESHOLD_YAML:   - NumSpills:       '1'
 ; THRESHOLD_YAML:   - String:          ' spills '
+; THRESHOLD_YAML:   - SpillsLocationCost: '1.000000e+04'
+; THRESHOLD_YAML:   - String:          ' spills location cost '
 ; THRESHOLD_YAML:   - NumReloads:      '1'
 ; THRESHOLD_YAML:   - String:          ' reloads '
+; THRESHOLD_YAML:   - ReloadsLocationCost: '1.000000e+04'
+; THRESHOLD_YAML:   - String:          ' reloads location cost '
 ; THRESHOLD_YAML:   - String:          generated in loop
 ; THRESHOLD_YAML: ...
 
 define void @fpr128(<4 x float>* %p) nounwind ssp !prof !11 !dbg !6 {
 entry:
   br label %loop, !dbg !8
 
 loop:

llvm/test/CodeGen/X86/statepoint-ra.ll

 ; RUN: llc -verify-machineinstrs -O3 -use-registers-for-deopt-values -restrict-statepoint-remat=true -pass-remarks-filter=regalloc -pass-remarks-output=%t.yaml -stop-after=greedy -o - < %s 2>&1 | FileCheck %s
 ; RUN: cat %t.yaml | FileCheck -check-prefix=YAML %s
 
 target triple = "x86_64-unknown-linux-gnu"
 
 ;CHECK-NOT: error: ran out of registers during register allocation
 
 ;YAML: --- !Missed
 ;YAML: Pass:            regalloc
 ;YAML: Name:            SpillReloadCopies
 ;YAML: Function:        barney
 ;YAML: Args:
 ;YAML:   - NumSpills:       '10'
 ;YAML:   - String:          ' spills '
+;YAML:   - SpillsLocationCost: '7.000000e+00'
+;YAML:   - String:          ' spills location cost '
 ;YAML:   - NumReloads:      '7'
 ;YAML:   - String:          ' reloads '
+;YAML:   - ReloadsLocationCost: '3.109004e-15'
+;YAML:   - String:          ' reloads location cost '
 ;YAML:   - NumZeroCostFoldedReloads: '20'
 ;YAML:   - String:          ' zero cost folded reloads '
 ;YAML:   - NumVRCopies:     '2'
 ;YAML:   - String:          ' virtual registers copies '
+;YAML:   - CopiesLocationCost: '8.882868e-16'
+;YAML:   - String:          ' copies location cost '
 ;YAML:   - String:          generated in function
 
 define void @barney(i8 addrspace(1)* %arg, double %arg1, double %arg2, double %arg3, double %arg4, double %arg5, double %arg6, double %arg7, double %arg8, double %arg9, double %arg10, double %arg11, double %arg12) gc "statepoint-example" personality i32* ()* @widget {
 bb:
   %tmp = call coldcc token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* nonnull @blam, i32 0, i32 0, i32 0, i32 0) [ "deopt"(i32 0, i32 1, i32 0, i32 0, i32 0, i32 26, i32 0, i32 0, i8 addrspace(1)* %arg, i32 4, double %arg1, i32 7, i8* null, i32 4, double %arg2, i32 7, i8* null, i32 4, double %arg3, i32 7, i8* null, i32 4, double %arg4, i32 7, i8* null, i32 4, double %arg5, i32 7, i8* null, i32 4, double %arg6, i32 7, i8* null, i32 4, double %arg7, i32 7, i8* null, i32 4, double %arg8, i32 7, i8* null, i32 4, double %arg9, i32 7, i8* null, i32 4, double %arg10, i32 7, i8* null, i32 4, double %arg11, i32 7, i8* null, i32 4, double %arg12, i32 7, i8* null, i32 7, i8* null), "gc-live"(i8 addrspace(1)* %arg) ]
   br i1 undef, label %bb13, label %bb15
 
 bb13:                                             ; preds = %bb