In machine block placement, use 60% instead of 80% as the hot branch probability threshold when profile data is available.

[congh]

Summary

Currently the machine block placement pass in LLVM uses 80% as the hot branch probability. However, I found that when profile data is available, we can decrease this threshold to get better performance. I modified this threshold into 50%/60%/70%, and use them to measure frontend stalls for SPEC2000 benchmarks. The average number of stalls generally decreases as we use smaller threshold. Below is my experiment results:

Hot branch prob threshold | # of frontend stalls change comparing to when using 80%
50% | +0.6%
60% | -2.2%
70% | -1.8%

Here we can see by using 60% we can get the smallest number of frontend stalls for SPEC2000. Hence in this patch I use 60% as the threshold when profile data is available.

[bkramer]

We use 80% as the 'hot' probability in many places. Would it make sense to add a getHotProbability(bool HasProfileData) to BranchProb so we can remove the magic numbers here? No need to do that in this patch but maybe in a follow-up.

Then we can check if the other users of 80% can also make smarter decisions when they know the probabilities come from prof data.

[congh]

Thanks for the review!

In D13791#268719, @bkramer wrote:

We use 80% as the 'hot' probability in many places. Would it make sense to add a getHotProbability(bool HasProfileData) to BranchProb so we can remove the magic numbers here? No need to do that in this patch but maybe in a follow-up.

Then we can check if the other users of 80% can also make smarter decisions when they know the probabilities come from prof data.

I am not sure if using the same "hot" probability in other places is a good idea as I am not sure how it is used there. After all, "hot" has different definitions depending on its context. But it is a good idea to at least try it.

[congh]

Ping?

[davidxl]

Changing the default requires more benchmarking results. Can you provide the numbers?

lib/CodeGen/MachineBlockPlacement.cpp

class MachineBlockPlacement : public MachineFunctionPass {
   /// \brief Function wide BasicBlock to BlockChain mapping.
   ///
   /// This mapping allows efficiently moving from any given basic block to the
   /// BlockChain it participates in, if any. We use it to, among other things,
   /// allow implicitly defining edges between chains as the existing edges
   /// between basic blocks.
   DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
 
+  /// \brief A flag indicating if the function being processes has profile data.
+  bool HasProfileData = false;
+
   void markChainSuccessors(BlockChain &Chain, MachineBasicBlock *LoopHeaderBB,
                            SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
                            const BlockFilterSet *BlockFilter = nullptr);
   MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB,
                                          BlockChain &Chain,
                                          const BlockFilterSet *BlockFilter);
   MachineBasicBlock *
   selectBestCandidateBlock(BlockChain &Chain,

 /// breaking CFG structure, but cave and break such structures in the case of
 /// very hot successor edges.
 ///
 /// \returns The best successor block found, or null if none are viable.
 MachineBasicBlock *
 MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
                                            BlockChain &Chain,
                                            const BlockFilterSet *BlockFilter) {
-  const BranchProbability HotProb(4, 5); // 80%
+  // Use 60% if profile data is available, otherwise 80%.
+  const BranchProbability HotProb =
+      HasProfileData ? BranchProbability(3, 5) : BranchProbability(4, 5);
 
   MachineBasicBlock *BestSucc = nullptr;
   // FIXME: Due to the performance of the probability and weight routines in
   // the MBPI analysis, we manually compute probabilities using the edge
   // weights. This is suboptimal as it means that the somewhat subtle
   // definition of edge weight semantics is encoded here as well. We should
   // improve the MBPI interface to efficiently support query patterns such as
   // this.
for (MachineBasicBlock *Succ : BB->successors()) {
     // any CFG constraints.
     if (SuccChain.LoopPredecessors != 0) {
       if (SuccProb < HotProb) {
         DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> " << SuccProb
                      << " (prob) (CFG conflict)\n");
         continue;
       }
 
-      // Make sure that a hot successor doesn't have a globally more
-      // important predecessor.
+      // Make sure that a hot successor doesn't have a globally more important
+      // predecessor.
+      assert(HotProb.getDenominator() == HotProb.getCompl().getDenominator());
+      assert(HotProb > BranchProbability(1, 2));
+      const BranchProbability ColdToHotRatio(HotProb.getCompl().getNumerator(),
+                                             HotProb.getNumerator());
       BlockFrequency CandidateEdgeFreq =
-          MBFI->getBlockFreq(BB) * SuccProb * HotProb.getCompl();
+          MBFI->getBlockFreq(BB) * SuccProb * ColdToHotRatio;
       bool BadCFGConflict = false;
       for (MachineBasicBlock *Pred : Succ->predecessors()) {
         if (Pred == Succ || (BlockFilter && !BlockFilter->count(Pred)) ||
             BlockToChain[Pred] == &Chain)
           continue;
         BlockFrequency PredEdgeFreq =
             MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ);
         if (PredEdgeFreq >= CandidateEdgeFreq) {
if (skipOptnoneFunction(*F.getFunction()))
     return false;
 
   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
   MLI = &getAnalysis<MachineLoopInfo>();
   TII = F.getSubtarget().getInstrInfo();
   TLI = F.getSubtarget().getTargetLowering();
   MDT = &getAnalysis<MachineDominatorTree>();
+  HasProfileData = static_cast<bool>(F.getFunction()->getEntryCount());
   assert(BlockToChain.empty());
 
   buildCFGChains(F);
 
   BlockToChain.clear();
   ChainAllocator.DestroyAll();
 
   if (AlignAllBlock)

test/CodeGen/AArch64/fast-isel-branch-cond-split.ll

bb3:
   ret i64 0
 
 bb4:
   %2 = call i64 @bar()
   ret i64 %2
 }
 
 ; CHECK-LABEL: test_and
-; CHECK:       cbz w0, {{LBB[0-9]+_2}}
-; CHECK:       cbnz w1, {{LBB[0-9]+_3}}
+; CHECK:       cbnz w0, {{LBB[0-9]+_2}}
+; CHECK:       cbz w1, {{LBB[0-9]+_1}}
 define i64 @test_and(i32 %a, i32 %b) {
 bb1:
   %0 = icmp ne i32 %a, 0
   %1 = icmp ne i32 %b, 0
   %or.cond = and i1 %0, %1
   br i1 %or.cond, label %bb4, label %bb3, !prof !1
 
 bb3: