[MachineSink+PGO] Teach MachineSink to use BlockFrequencyInfo

[bruno]

Summary

Teach MachineSink to use BlockFrequencyInfo

Machine Sink uses loop depth information to select between successors BBs to sink machine instructions into, where BBs within smaller loop depths are preferable.
This patch adds support for choosing between successors by using profile information from BlockFrequencyInfo instead, whenever the information is available.

Tested it under SPEC2006 train (average of 30 runs for each program). The baseline uses -O3 and PGO without Machine Sink support. There are no regressions found for these programas, and the speedup follows:

benchmark Speedup (Relative change)
400.perlbench 2.49%
401.bzip2 2.59%
403.gcc 2.43%
429.mcf 2.56%
456.hmmer 2.38%
458.sjeng 1.75%
462.libquantum 0.08%
464.h264ref 2.65%
471.omnetpp 1.00%
473.astar 1.81%
483.xalancbmk 1.00%
433.milc 1.44%
444.namd 1.60%
450.soplex 1.63%
470.lbm 1.65%
GeoMean 1.49%

More details on the results at http://pastebin.com/VQBfU4PH

[chandlerc]

This seems fine in general.

Could you include a (admitedly contrived) test case that exercises the two
paths?

[qcolombet]

Same comment as Chandler.

Thanks Bruno,
-Quentin

[bruno]

Thanks for the feedback,

Updated the patch to include a test-case.

Manman, they're collected with train data and tested on train data.
Chad, I've tested it only on darwin x86-64.

[qcolombet]

lib/CodeGen/MachineSink.cpp

260

Should we still grab this analysis if UseBlockFreqInfo is false?

588–593

If we do not grab the analysis when UseBlockFreqInfo is false, this should be adapted.

test/CodeGen/X86/sink-blockfreq.ll

2

Put -machine-sink-bfi=true on the run line. Although this is not required, I like being explicit with what we test.

[bruno]

New patch version, updated after Quentin's comments

[qcolombet]

Hi Bruno,

Thanks for the quick update.

LGTM.

One remark:
uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;

We could avoid the penalty of checking whether or not MBFI is available for each tested pair by setting different call backs (one that always returns 0, and one that returns the actual frequency). Those callbacks would be set once in the beginning of runOnMachineFunction, hence having MBFI tested only once. I do not think this will have a measurable impact for most cases. So, this is fine to leave that like this, moreover, if you plan to kill the option, this won’t be necessary anymore :).

Thanks,
-Quentin

[bruno]

Hi Quentin,

Thanks again, I'll kill the option hopefully soon.
Committed in r218472

lib/CodeGen/MachineSink.cpp

 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachinePostDominators.h"

            cl::desc("Split critical edges during machine sinking"),
            cl::init(true), cl::Hidden);
 
+static cl::opt<bool>
+UseBlockFreqInfo("machine-sink-bfi",
+           cl::desc("Use block frequency info to find successors to sink"),
+           cl::init(true), cl::Hidden);
+
+
 STATISTIC(NumSunk,      "Number of machine instructions sunk");
 STATISTIC(NumSplit,     "Number of critical edges split");
 STATISTIC(NumCoalesces, "Number of copies coalesced");

     MachineDominatorTree *DT;      // Machine dominator tree
     MachinePostDominatorTree *PDT; // Machine post dominator tree
     MachineLoopInfo *LI;
+    const MachineBlockFrequencyInfo *MBFI;
     AliasAnalysis *AA;
 
     // Remember which edges have been considered for breaking.

       AU.addPreserved<MachineDominatorTree>();
       AU.addPreserved<MachinePostDominatorTree>();
       AU.addPreserved<MachineLoopInfo>();
+      if (UseBlockFreqInfo)
+        AU.addRequired<MachineBlockFrequencyInfo>();
     }
 
     void releaseMemory() override {

   DT = &getAnalysis<MachineDominatorTree>();
   PDT = &getAnalysis<MachinePostDominatorTree>();
   LI = &getAnalysis<MachineLoopInfo>();
+  MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
   AA = &getAnalysis<AliasAnalysis>();
 
   bool EverMadeChange = false;

       }
 
       // Otherwise, we should look at all the successors and decide which one
-      // we should sink to.
-      // We give successors with smaller loop depth higher priority.
-      SmallVector<MachineBasicBlock*, 4> Succs(MBB->succ_begin(), MBB->succ_end());
-      // Sort Successors according to their loop depth.
+      // we should sink to. If we have reliable block frequency information
+      // (frequency != 0) available, give successors with smaller frequencies
+      // higher priority, otherwise prioritize smaller loop depths.
+      SmallVector<MachineBasicBlock*, 4> Succs(MBB->succ_begin(),
+                                               MBB->succ_end());
+      // Sort Successors according to their loop depth or block frequency info.
       std::stable_sort(
           Succs.begin(), Succs.end(),
-          [this](const MachineBasicBlock *LHS, const MachineBasicBlock *RHS) {
-            return LI->getLoopDepth(LHS) < LI->getLoopDepth(RHS);
+          [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
+            uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
+            uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
+            bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
+            return HasBlockFreq ? LHSFreq < RHSFreq
+                                : LI->getLoopDepth(L) < LI->getLoopDepth(R);
           });
       for (SmallVectorImpl<MachineBasicBlock *>::iterator SI = Succs.begin(),
              E = Succs.end(); SI != E; ++SI) {

test/CodeGen/X86/sink-blockfreq.ll

+; RUN: llc -disable-machine-licm -machine-sink-bfi=true -mtriple=x86_64-apple-darwin < %s | FileCheck %s -check-prefix=MSINK_BFI
+; RUN: llc -disable-machine-licm -machine-sink-bfi=false -mtriple=x86_64-apple-darwin < %s | FileCheck %s -check-prefix=MSINK_NOBFI
+
+; Test that by changing BlockFrequencyInfo we change the order in which
+; machine-sink looks for sucessor blocks. By not using BFI, both G and B
+; have the same loop depth and no instructions is sinked - B is selected but
+; can't be used as to avoid breaking a non profitable critical edge. By using
+; BFI, "mul" is sinked into the less frequent block G.
+define i32 @sink_freqinfo(i32 %a, i32 %b) nounwind uwtable ssp {
+; MSINK_BFI-LABEL: sink_freqinfo
+; MSINK_BFI: jl
+; MSINK_BFI-NEXT: ## BB#
+; MSINK_BFI-NEXT: imull
+
+; MSINK_NOBFI-LABEL: sink_freqinfo
+; MSINK_NOBFI: imull
+; MSINK_NOBFI: jl
+entry:
+  br label %B
+
+B:
+  %ee = phi i32 [ 0, %entry ], [ %inc, %F ]
+  %xx = sub i32 %a, %ee
+  %cond0 = icmp slt i32 %xx, 0
+  br i1 %cond0, label %F, label %exit, !prof !0
+
+F:
+  %inc = add nsw i32 %xx, 2
+  %aa = mul nsw i32 %b, %inc
+  %exitcond = icmp slt i32 %inc, %a
+  br i1 %exitcond, label %B, label %G, !prof !1
+
+G:
+  %ii = add nsw i32 %aa, %a
+  %ll = add i32 %b, 45
+  %exitcond2 = icmp sge i32 %ii, %b
+  br i1 %exitcond2, label %G, label %exit, !prof !2
+
+exit:
+  ret i32 0
+}
+
+!0 = metadata !{metadata !"branch_weights", i32 4, i32 1}
+!1 = metadata !{metadata !"branch_weights", i32 128, i32 1}
+!2 = metadata !{metadata !"branch_weights", i32 1, i32 1}