Disable hoisting MI to hotter basic blocks

[NeHuang]

Summary

In current Hoist() function of machine licm pass, it will not check the source and destination basic block frequencies that a instruction is hoisted from/to. There is a chance that instruction is hoisted from a cold to a hot basic block.

In this patch, we add options to disable machine instruction hoisting if destination block is hotter.

[nemanjai]

Added a couple more reviewers that either recently modified this file or I think may be interested in the proposed change.

[NeHuang]

ping

[NeHuang]

ping

[efriedma]

In the future, please try to ping more frequently than once a month; we don't want to lose patches, even if there are some areas where it takes a while to get review.

The general idea of avoiding hoisting that would increase the frequency makes sense.

Could you give some idea what effect this has in practice? How often does this trigger on SPEC? Does it affect SPEC performance or size numbers? (Replace SPEC with some similar benchmark if you prefer.)

Is there anything special about the number "100"?

[NeHuang]

Thanks @efriedma for the review and remind.

This patch adds an option to disable non-profitable hoisting from a cold to a hot basic block.

The stats below is collected based on Google benchmark. (The 3rd column indicates number of hoisting is disabled due to block frequency hotness, results varies from the loads of different benchmarks)

Benchmark	Number of machine instructions hoisted out of loops	Number of instructions not hoisted due to block frequency hotness
Protobuf	20931	1706
Brotli	9935	17616
Gipfeli	471	879
snappy	886	1154
TCMalloc	6435	891
BoringSSL	6115	501
FFMPEG	8324	17

With the patch enabled, we found SPEC2017 performance gain for PPC.

'100' is the block-freq-ratio-threshold used in our experiment to determine when to disable the hoisting, which is a configurable option.

[Whitney]

llvm/lib/CodeGen/MachineLICM.cpp

53 ↗

(On Diff #206082)

Please run clang-format on your change. The include is not added at the right place.

1585 ↗

(On Diff #206082)

Change to ++ NumNotHoistedDueToHotness

[NeHuang]

This comment was removed by NeHuang.

llvm/lib/CodeGen/MachineLICM.cpp

53 ↗

(On Diff #206082)

Done.

1585 ↗

(On Diff #206082)

Done

[jsji]

machinelicm_clangformat_modv1.cpp ? I think you uploaded wrong patch.

[NeHuang]

@jsji Yes, please ignore diff 216684. Thanks you for the remind.

Thanks @Whitney for the review. Addressed the comment and uploaded diff 216693.

[lei]

llvm/lib/CodeGen/MachineLICM.cpp

92 ↗

(On Diff #216693)

indentation

111 ↗

(On Diff #216693)

nit: please follow the same indentation as the lines above.

1572 ↗

(On Diff #216693)

nit: Most of the functions here use either BB or MBB for MachineBasicBlock variables. IMHO unless there are diff BBs that are being tracked, I don't see why we need to specify this as "current"BB. Just makes it easier to read when similar variables are being used consistently.

[lebedev.ri]

Just passing-by remark: i find naming schemes in this patch very confusing:

• The patch subject should talk about not hoisting into hotter blocks, not about early out
• due to block hotness is very meaningless to me. I suspect most of the occurrences of that phrase should actually be closer to because destination block is hotter

llvm/lib/CodeGen/MachineLICM.cpp

81–82 ↗

(On Diff #216693)

It isn't really obvious whether larger value relaxes this check or the other way around

[NeHuang]

Thanks @lei for the review. Updated the patch to r

1. Resolve the indentation issues
2. Modify the variable name to be consistent with current naming convention.

Thanks @lebedev.ri for your review. Subject and summary have been updated accordingly.
For the BlockFrequencyRatioThreshold, larger value will relax the check. For example, by default, it will disable MI hoisting if destination block is 100 times hotter than source block.

[NeHuang]

llvm/lib/CodeGen/MachineLICM.cpp

92 ↗

(On Diff #216693)

Done

111 ↗

(On Diff #216693)

Done

[NeHuang]

llvm/lib/CodeGen/MachineLICM.cpp

1572 ↗

(On Diff #216693)

Done

[NeHuang]

llvm/lib/CodeGen/MachineLICM.cpp

1572 ↗

(On Diff #216693)

Done

[nemanjai]

Some minor changes are required to make it more clear what this does.

llvm/lib/CodeGen/MachineLICM.cpp

85 ↗

(On Diff #220032)

Similarly to below, the naming is a bit strange. Perhaps:

enum DisableHoistingToHotterBlocks { None, PGO, All };

or

enum DisableHoistingToHotterBlocks { None, PGO_Only, Static };

(although I prefer the former).

88 ↗

(On Diff #220032)

The name sounds very strange. Perhaps:

DisableHoistingToHotterBlocks("disable-hoisting-to-hotter-blocks",

112 ↗

(On Diff #220032)

"block frequency hotness" sounds strange. Please use either "hotness" or "block frequency".

275 ↗

(On Diff #220032)

I think it is clearer to just use SrcBlock and TgtBlock for the names of the blocks.

1471 ↗

(On Diff #220032)

Presumably this function is called many times for the same function and we are querying the function for profile data every time. Would it be possible to just have a class member flag for whether the function has profile data or not?

1581 ↗

(On Diff #220032)

We don't want to increment the statistic here?

Honestly, I don't think we should be incrementing the statistic in this function at all - this is just a query for whether or not this is profitable. Strictly speaking, the increment to the statistic really belongs in the function that would actually do the hoisting (i.e. Hoist()).

1585 ↗

(On Diff #220032)

If we move the update to the statistic out of this function, this can probably just be changed to:
return Ratio > BlockFrequencyRatioThreshold;

81–82 ↗

(On Diff #216693)

We should probably be more forthcoming with this description so that it is clear to the user.
Perhaps:

Do not hoist instructions if the target block is N times hotter than the source.

Also, we should add a comment here along the lines of:

// The default threshold of 100 (i.e. if target block is 100 times hotter)
// is based on empirical data on a single target and is subject to tuning.

[NeHuang]

Addressed @nemanjai 's review comment.

[NeHuang]

Thanks @nemanjai 's review. Addressed all the comments and updated the test cases accordingly.

llvm/lib/CodeGen/MachineLICM.cpp

85 ↗

(On Diff #220032)

• Using "DisableHositingToHotterBlocksType" for enum
• Using"NONE" instead of "None" to avoid ambiguity.

[NeHuang]

Collected stats below for SPECInt and SPECFP benchmarks (SPEC2017) with this feature enabled, compiled with -O3 and PGO.

Benchmark	Number of machine instructions hoisted out of loops	Number of instructions not hoisted due to block frequency
SPECInt	129269	459891
SPECFP	36047	70075

[lebedev.ri]

In D63676#1679799, @NeHuang wrote:

Collected stats below for SPECInt and SPECFP benchmarks (SPEC2017) with this feature enabled, compiled with -O3 and PGO.

Benchmark	Number of machine instructions hoisted out of loops	Number of instructions not hoisted due to block frequency
SPECInt	129269	459891
SPECFP	36047	70075

I think this might be a bit context-less, as in what are the numbers without the patch?

[NeHuang]

• Merged to latest code base and compiled with -O3 and PGO
• Collected stats for SPECInt and SPECFP benchmarks (SPEC2017) with baseline and patch.

Benchmark	Number of machine instructions hoisted out of loops (Baseline)	Number of machine instructions hoisted out of loops (Patch)	Number of instructions not hoisted to hotter destination (Patch)
SPECInt	206914	132007	476157
SPECFP	42591	36383	68215

• With the feature enabled, found performance gain for SPEC benchmarks, e.g. 2.1% for perlbench_r and 1.6% for povray_r.

[nemanjai]

With the minor comments addressed, this LGTM.
However before you update and commit, it would be good to hear from at least @lebedev.ri about whether his requests were satisfactorily met.

llvm/lib/CodeGen/MachineLICM.cpp

87 ↗

(On Diff #221407)

It is common practice to differentiate enumerators in one of two ways:

1. Prefix each enumerator with an acronym of the enumeration
2. Use scoped enumerations

While we're at it, you might as well simplify the naming to just UseBFI
Examples (with simplified name):

1. enum UseBFI { UseBFI_None, UseBFI_PGO, UseBFI_All }
2. enum class UseBFI { None, PGO, All }

My preference is 2.

91 ↗

(On Diff #221407)

Please replace all uses of the word hosting with the word hoisting since we are changing the decisions about hoisting instructions out of loops. In addition to correcting it in code, please correct it in the description, title, commit message, etc.

126 ↗

(On Diff #221407)

Nit: naming convention (variables still start with uppercase letters).

278 ↗

(On Diff #221407)

Nit: naming convention - functions start with a lowercase letter. And since this doesn't do any hoisting, I think a simpler name would be more appropriate. Perhaps

// Is the target basic block at least "BlockFrequencyRatioThreshold" times
// hotter than the source basic block.
bool isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,
                        MachineBasicBlock *TgtBlock);

1578 ↗

(On Diff #221407)

This indentation is suspicious. If that's where clang-format put this line, so be it, but it just seems odd.

[NeHuang]

Addressed review comments from @nemanjai

@lebedev.ri I have re-collected stats for SPECInt and SPECFP benchmarks with baseline and patch. Table summarized above.

[NeHuang]

ping

[NeHuang]

Since the patch is approved, I will hold it for another 3 days if any comment and commit it on Monday.

[xbolva00]

This is disabled by default for non-PGO builds, right? Did you try to benchmark the patch for non PGO mode? There are various heuristic already in LLVM which are enabled for non-PGO mode too if they generally improve the perf.

[NeHuang]

Thanks @xbolva00 for your comment.

"This is disabled by default for non-PGO builds, right?"
Yes, it is disabled for non-pgo by default.

Did you try to benchmark the patch for non PGO mode? There are various heuristic already in LLVM which are enabled for non-PGO mode too if they generally improve the perf.
Yes, I did. For non-pgo mode, there are no significant improvements and one noticeable degradation for benchmark povray (4.7% degradation)

[xbolva00]

Ok, thanks for info!

machinelicm_clangformat_modv1.cpp

 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineOperand.h"
SinkInstsToAvoidSpills("sink-insts-to-avoid-spills",
                        cl::desc("MachineLICM should sink instructions into "
                                 "loops to avoid register spills"),
                        cl::init(false), cl::Hidden);
 static cl::opt<bool>
 HoistConstStores("hoist-const-stores",
                  cl::desc("Hoist invariant stores"),
                  cl::init(true), cl::Hidden);
 
+static cl::opt<unsigned>
+BlockFrequencyRatioThreshold("block-freq-ratio-threshold",
+                 cl::desc("Block frequency ratio threshold to "
+                    "disable instruction hoisting"),
+                 cl::init(100), cl::Hidden);
+
+enum NotHoistDueToBlockHotnessType { Disable, Enable_PGO, Enable };
+
+static cl::opt<NotHoistDueToBlockHotnessType>
+NotHoistDueToBlockHotness("not-hoist-due-to-block-hotness",
+                cl::desc("Disable instruction hoist due to block hotness"),
+                cl::init(Disable), cl::Hidden,
+                cl::values(clEnumValN(Disable, "disable",
+         "disable the feature"),
+                           clEnumValN(Enable_PGO, "enable-pgo",
+         "enable the feature when using profile data"),
+                           clEnumValN(Enable, "enable",
+         "enable the feature with/without profile data")));
+
 STATISTIC(NumHoisted,
           "Number of machine instructions hoisted out of loops");
 STATISTIC(NumLowRP,
           "Number of instructions hoisted in low reg pressure situation");
 STATISTIC(NumHighLatency,
           "Number of high latency instructions hoisted");
 STATISTIC(NumCSEed,
           "Number of hoisted machine instructions CSEed");
 STATISTIC(NumPostRAHoisted,
           "Number of machine instructions hoisted out of loops post regalloc");
 STATISTIC(NumStoreConst,
           "Number of stores of const phys reg hoisted out of loops");
+STATISTIC(NumNotHoistedDueToHotness,
+    "Number of instructions not hoisted due to block frequency hotness");
 
 namespace {
 
   class MachineLICMBase : public MachineFunctionPass {
     const TargetInstrInfo *TII;
     const TargetLoweringBase *TLI;
     const TargetRegisterInfo *TRI;
     const MachineFrameInfo *MFI;
     MachineRegisterInfo *MRI;
     TargetSchedModel SchedModel;
     bool PreRegAlloc;
 
     // Various analyses that we use...
     AliasAnalysis        *AA;      // Alias analysis info.
+    MachineBlockFrequencyInfo *MBFI; // Machine block frequncy info
     MachineLoopInfo      *MLI;     // Current MachineLoopInfo
     MachineDominatorTree *DT;      // Machine dominator tree for the cur loop
 
     // State that is updated as we process loops
     bool         Changed;          // True if a loop is changed.
     bool         FirstInLoop;      // True if it's the first LICM in the loop.
     MachineLoop *CurLoop;          // The current loop we are working on.
     MachineBasicBlock *CurPreheader; // The preheader for CurLoop.
namespace {
   public:
     MachineLICMBase(char &PassID, bool PreRegAlloc)
         : MachineFunctionPass(PassID), PreRegAlloc(PreRegAlloc) {}
 
     bool runOnMachineFunction(MachineFunction &MF) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<MachineLoopInfo>();
+      if (NotHoistDueToBlockHotness != Disable)
+        AU.addRequired<MachineBlockFrequencyInfo>();
       AU.addRequired<MachineDominatorTree>();
       AU.addRequired<AAResultsWrapperPass>();
       AU.addPreserved<MachineLoopInfo>();
       AU.addPreserved<MachineDominatorTree>();
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
     void releaseMemory() override {
bool EliminateCSE(
         DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI);
 
     bool MayCSE(MachineInstr *MI);
 
     bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader);
 
     void InitCSEMap(MachineBasicBlock *BB);
 
+    bool IsHoistingFromColdToHotBlock(MachineBasicBlock *CurBB,
+                                      MachineBasicBlock *Preheader);
+
     MachineBasicBlock *getCurPreheader();
   };
 
   class MachineLICM : public MachineLICMBase {
   public:
     static char ID;
     MachineLICM() : MachineLICMBase(ID, false) {
       initializeMachineLICMPass(*PassRegistry::getPassRegistry());

 char EarlyMachineLICM::ID;
 
 char &llvm::MachineLICMID = MachineLICM::ID;
 char &llvm::EarlyMachineLICMID = EarlyMachineLICM::ID;
 
 INITIALIZE_PASS_BEGIN(MachineLICM, DEBUG_TYPE,
                       "Machine Loop Invariant Code Motion", false, false)
 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(MachineLICM, DEBUG_TYPE,
                     "Machine Loop Invariant Code Motion", false, false)
 
 INITIALIZE_PASS_BEGIN(EarlyMachineLICM, "early-machinelicm",
                       "Early Machine Loop Invariant Code Motion", false, false)
 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(EarlyMachineLICM, "early-machinelicm",
                     "Early Machine Loop Invariant Code Motion", false, false)
 
 /// Test if the given loop is the outer-most loop that has a unique predecessor.
 static bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) {
   // Check whether this loop even has a unique predecessor.
if (PreRegAlloc) {
     RegPressure.resize(NumRPS);
     std::fill(RegPressure.begin(), RegPressure.end(), 0);
     RegLimit.resize(NumRPS);
     for (unsigned i = 0, e = NumRPS; i != e; ++i)
       RegLimit[i] = TRI->getRegPressureSetLimit(MF, i);
   }
 
   // Get our Loop information...
+  if (NotHoistDueToBlockHotness != Disable)
+    MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
   MLI = &getAnalysis<MachineLoopInfo>();
   DT  = &getAnalysis<MachineDominatorTree>();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 
   SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());
   while (!Worklist.empty()) {
     CurLoop = Worklist.pop_back_val();
     CurPreheader = nullptr;
bool MachineLICMBase::MayCSE(MachineInstr *MI) {
 
   return LookForDuplicate(MI, CI->second) != nullptr;
 }
 
 /// When an instruction is found to use only loop invariant operands
 /// that are safe to hoist, this instruction is called to do the dirty work.
 /// It returns true if the instruction is hoisted.
 bool MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
+  MachineBasicBlock *CurBB = MI->getParent();
+  bool hasProfileData = CurBB->getParent()->getFunction().hasProfileData();
+
+  // Disable the instruction hoisting due to block hotness
+  if ((NotHoistDueToBlockHotness == Enable ||
+      (NotHoistDueToBlockHotness == Enable_PGO && hasProfileData)) &&
+      IsHoistingFromColdToHotBlock(CurBB, Preheader))
+    return false;
+
   // First check whether we should hoist this instruction.
   if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) {
     // If not, try unfolding a hoistable load.
     MI = ExtractHoistableLoad(MI);
     if (!MI) return false;
   }
 
   // If we have hoisted an instruction that may store, it can only be a constant
if (!CurPreheader) {
         CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
         return nullptr;
       }
     }
   }
   return CurPreheader;
 }
 
+bool MachineLICMBase::IsHoistingFromColdToHotBlock(MachineBasicBlock *CurBB,
+    MachineBasicBlock *Preheader) {
+  // Parse source and target basic block frequency from MBFI
+  uint64_t SrcBF = MBFI->getBlockFreq(CurBB).getFrequency();
+  uint64_t DstBF = MBFI->getBlockFreq(Preheader).getFrequency();
+
+  // Disable the hoisting if source block frequency is zero
+  if (!SrcBF)
+    return true;
+
+  double Ratio = (double)DstBF / SrcBF;
+  // Compare the block frequency ratio with the threshold
+  if (Ratio > BlockFrequencyRatioThreshold) {
+    ++NumNotHoistedDueToHotness;
+    return true;
+  }
+
+  return false;
+}
+