[MBP] Use profile count to compute tail dup cost if it is available

[Carrot]

Summary

Current tail duplication in machine block placement pass uses block frequency information in cost model. But frequency number has only relative meaning compared to other basic blocks in the same function. A large frequency number doesn't mean it is hot and a small frequency number doesn't mean it is cold.

To overcome this problem, this patch uses profile count in cost model if it's available. So we can tail duplicate real hot basic blocks.

When tested with spec2006int, the performance doesn't change, the number of tail duplicated blocks was reduced from 2376 to 1746.

In our internal testing, search1 was not impacted, search2 was improved by 0.1%, another 0.1% can be achieved with larger threshold parameter.

[davidxl]

A few things:

1. can this be extended to the TailDup pass too?
2. what is the impact on text size?
3. what is the performance with AFDO and XFDO?

4. Can the threshold be tuned higher (with more performnace)?

llvm/lib/CodeGen/MachineBlockPlacement.cpp

420

This should probbaly return Optional<..>

426

Return None here. Also when None is returned, I think the caller needs to handle it conservatively -- perhaps resort to Freq based method

3167

Is this change related?

[Carrot]

In D83265#2144298, @davidxl wrote:

A few things:

1. can this be extended to the TailDup pass too?

This patch only changes the cost function, it doesn't change tail dup algorithms, especially the partial duplication is not implemented in TailDup pass.

2. what is the impact on text size?

The total text size of spec2006int is reduced by 7804 bytes.

3. what is the performance with AFDO and XFDO?

The performance benefit depends on the precision of profile count. So I expect the performance gain with AFDO is similar to FDO. But XFDO has less accurate profile count, so it should has less performance gain.

4. Can the threshold be tuned higher (with more performnace)?

The performance impact of tail duplication is mainly a function of two interfering factors, increased fall through (reduced taken branch) and increased code size (less effective usage of instruction cache).
For small binaries, the instruction cache is not a problem, so they prefer more tail duplications, thus smaller TailDupProfileCountThreshold.
For large binaries, it's not a good idea to trade a small number of increased fall through for worse instruction cache behavior. So we need to increase the bar for tail duplication, thus larger TailDupProfileCountThreshold.
The current default value of TailDupProfileCountThreshold is tuned to keep spec2006int not impacted, while still has 0.1% perf win for Goolge search benchmark. I can get another 0.1% improvement for the search benchmark if I increase TailDupProfileCountThreshold to 500.

llvm/lib/CodeGen/MachineBlockPlacement.cpp

420

See following reply.

426

Look at the implementation of getBlockProfileCount and getBlockFreq.

BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {

return BFI ? BFI->getBlockFreq(BB) : 0;

}

Optional<uint64_t>
BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB,

                                       bool AllowSynthetic) const {
if (!BFI)
  return None;

return BFI->getBlockProfileCount(*getFunction(), BB, AllowSynthetic);

}

In the same condition (!BFI), neither function returns meaningful result, but one returuns None, another returns 0.

Another situation None may be returned is the function has no profile count, so the result is actually a meaningful 0.

3167

It is not profile count cost model related.
It is a different tail dup improvement.
Do you want me to send another patch for it?

[davidxl]

llvm/lib/CodeGen/MachineBlockPlacement.cpp

3167

Better separate it. Is the contributing to the performance improvement mentioned?

[Carrot]

llvm/lib/CodeGen/MachineBlockPlacement.cpp

3167

It doesn't cause visible performance impact.

[davidxl]

lgtm

llvm/lib/CodeGen/MachineBlockPlacement.cpp

181

Nit: TailDupProfilePercentThreshold

[Carrot]

Will commit this version.

llvm/lib/CodeGen/MachineBlockPlacement.cpp

static cl::opt<unsigned> TailDupPlacementPenalty(
     "tail-dup-placement-penalty",
     cl::desc("Cost penalty for blocks that can avoid breaking CFG by copying. "
              "Copying can increase fallthrough, but it also increases icache "
              "pressure. This parameter controls the penalty to account for that. "
              "Percent as integer."),
     cl::init(2),
     cl::Hidden);
 
+// Heuristic for tail duplication if profile count is used in cost model.
+static cl::opt<unsigned> TailDupProfileCountThreshold(
+    "tail-dup-profile-count-threshold",
+    cl::desc("If profile count information is used in tail duplication cost "
+             "model, the gained fall through number from tail duplication "
+             "should be at least this percent of hot count."),
+    cl::init(50),
+    cl::Hidden);
+
 // Heuristic for triangle chains.
 static cl::opt<unsigned> TriangleChainCount(
     "triangle-chain-count",
     cl::desc("Number of triangle-shaped-CFG's that need to be in a row for the "
              "triangle tail duplication heuristic to kick in. 0 to disable."),
     cl::init(2),
     cl::Hidden);
 
class MachineBlockPlacement : public MachineFunctionPass {
   /// Placement decisions can open up new tail duplication opportunities, but
   /// since tail duplication affects placement decisions of later blocks, it
   /// must be done inline.
   TailDuplicator TailDup;
 
   /// Partial tail duplication threshold.
   BlockFrequency DupThreshold;
 
+  /// True:  use block profile count to compute tail duplication cost.
+  /// False: use block frequency to compute tail duplication cost.
+  bool UseProfileCount;
+
   /// Allocator and owner of BlockChain structures.
   ///
   /// We build BlockChains lazily while processing the loop structure of
   /// a function. To reduce malloc traffic, we allocate them using this
   /// slab-like allocator, and destroy them after the pass completes. An
   /// important guarantee is that this allocator produces stable pointers to
   /// the chains.
   SpecificBumpPtrAllocator<BlockChain> ChainAllocator;

 #ifndef NDEBUG
   /// The set of basic blocks that have terminators that cannot be fully
   /// analyzed.  These basic blocks cannot be re-ordered safely by
   /// MachineBlockPlacement, and we must preserve physical layout of these
   /// blocks and their successors through the pass.
   SmallPtrSet<MachineBasicBlock *, 4> BlocksWithUnanalyzableExits;
 #endif
 
+  /// Get block profile count or frequency according to UseProfileCount.
+  /// The return value is used to model tail duplication cost.
+  BlockFrequency getBlockCountOrFrequency(const MachineBasicBlock *BB) {
+    if (UseProfileCount) {
+      auto Count = MBFI->getMBFI().getBlockProfileCount(BB);
+      if (Count)
+        return *Count;
+      else
+        return 0;
+    }
+    else
+      return MBFI->getBlockFreq(BB);
+  }
+
   /// Scale the DupThreshold according to basic block size.
   BlockFrequency scaleThreshold(MachineBasicBlock *BB);
   void initDupThreshold();
 
   /// Decrease the UnscheduledPredecessors count for all blocks in chain, and
   /// if the count goes to 0, add them to the appropriate work list.
   void markChainSuccessors(
       const BlockChain &Chain, const MachineBasicBlock *LoopHeaderBB,
for (MachineBasicBlock *Succ : Pred->successors())
     }
 
   BranchProbability BBProb = MBPI->getEdgeProbability(Pred, BB);
   if (BBProb <= BestProb)
     return false;
 
   // Compute the number of reduced taken branches if Pred falls through to BB
   // instead of another successor. Then compare it with threshold.
-  BlockFrequency PredFreq = MBFI->getBlockFreq(Pred);
+  BlockFrequency PredFreq = getBlockCountOrFrequency(Pred);
   BlockFrequency Gain = PredFreq * (BBProb - BestProb);
   return Gain > scaleThreshold(BB);
 }
 
 // Find out the predecessors of BB and BB can be beneficially duplicated into
 // them.
 void MachineBlockPlacement::findDuplicateCandidates(
     SmallVectorImpl<MachineBasicBlock *> &Candidates,
     MachineBasicBlock *BB,
     BlockFilterSet *BlockFilter) {
   MachineBasicBlock *Fallthrough = nullptr;
   BranchProbability DefaultBranchProb = BranchProbability::getZero();
   BlockFrequency BBDupThreshold(scaleThreshold(BB));
+
   SmallVector<MachineBasicBlock *, 8> Preds(BB->pred_begin(), BB->pred_end());
-  SmallVector<MachineBasicBlock *, 8> Succs(BB->succ_begin(), BB->succ_end());
+  SmallVector<MachineBasicBlock *, 8> Succs;
+  for (MachineBasicBlock *Succ : BB->successors()) {
+    if (BlockFilter && !BlockFilter->count(Succ))
+      continue;
+    BlockChain *SuccChain = BlockToChain[Succ];
+    if (SuccChain && (Succ != *SuccChain->begin()))
+      continue;
+    Succs.push_back(Succ);
+  }
 
   // Sort for highest frequency.
   auto CmpSucc = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
     return MBPI->getEdgeProbability(BB, A) > MBPI->getEdgeProbability(BB, B);
   };
   auto CmpPred = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
     return MBFI->getBlockFreq(A) > MBFI->getBlockFreq(B);
   };
void MachineBlockPlacement::findDuplicateCandidates(
   // duplicated into PB, and one successor is layout after it (SB1 for PB1 and
   // SB2 for PB2 in our case). If there is no available successor, the combined
   // block jumps to all BB's successor, like PB3 in this example.
   //
   // If a predecessor has multiple successors, so BB can't be duplicated into
   // it. But it can beneficially fall through to BB, and duplicate BB into other
   // predecessors.
   for (MachineBasicBlock *Pred : Preds) {
-    BlockFrequency PredFreq = MBFI->getBlockFreq(Pred);
+    BlockFrequency PredFreq = getBlockCountOrFrequency(Pred);
 
     if (!TailDup.canTailDuplicate(BB, Pred)) {
       // BB can't be duplicated into Pred, but it is possible to be layout
       // below Pred.
       if (!Fallthrough && isBestSuccessor(BB, Pred, BlockFilter)) {
         Fallthrough = Pred;
         if (SuccIt != Succs.end())
           SuccIt++;
void MachineBlockPlacement::findDuplicateCandidates(
   }
 }
 
 void MachineBlockPlacement::initDupThreshold() {
   DupThreshold = 0;
   if (!F->getFunction().hasProfileData())
     return;
 
+  // We prefer to use prifile count.
+  uint64_t HotThreshold = PSI->getOrCompHotCountThreshold();
+  if (HotThreshold != UINT64_MAX) {
+    UseProfileCount = true;
+    DupThreshold = HotThreshold * TailDupProfileCountThreshold / 100;
+    return;
+  }
+
+  // Profile count is not available, we can use block frequency instead.
   BlockFrequency MaxFreq = 0;
   for (MachineBasicBlock &MBB : *F) {
     BlockFrequency Freq = MBFI->getBlockFreq(&MBB);
     if (Freq > MaxFreq)
       MaxFreq = Freq;
   }
 
-  // FIXME: we may use profile count instead of frequency,
-  // and need more fine tuning.
   BranchProbability ThresholdProb(TailDupPlacementPenalty, 100);
   DupThreshold = MaxFreq * ThresholdProb;
+  UseProfileCount = false;
 }
 
 bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()))
     return false;
 
   // Check for single-block functions and skip them.
   if (std::next(MF.begin()) == MF.end())

llvm/test/CodeGen/X86/dup-cost.ll

+; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s
+
+; Cold function, %dup should not be duplicated into predecessors.
+define i32 @cold(i32 %a, i32* %p, i32* %q) !prof !21 {
+; CHECK-LABEL: cold
+; CHECK:       %entry
+; CHECK:       %true1
+; CHECK:       %dup
+; CHECK:       %true2
+; CHECK:       %false1
+; CHECK:       %false2
+entry:
+  %cond1 = icmp sgt i32 %a, 1
+  br i1 %cond1, label %true1, label %false1, !prof !30
+
+true1:
+  %v1 = load i32, i32* %p, align 4
+  %v2 = add i32 %v1, 2
+  br label %dup
+
+false1:
+  %v3 = load i32, i32* %q, align 4
+  %v4 = sub i32 %v3, 3
+  br label %dup
+
+dup:
+  %v5 = phi i32 [%v2, %true1], [%v4, %false1]
+  %cond2 = icmp sgt i32 %v5, 4
+  br i1 %cond2, label %true2, label %false2, !prof !30
+
+true2:
+  %v6 = xor i32 %v5, %a
+  br label %exit
+
+false2:
+  %v7 = and i32 %v5, %a
+  br label %exit
+
+exit:
+  %v8 = phi i32 [%v6, %true2], [%v7, %false2]
+  ret i32 %v8
+}
+
+; Same code as previous function, but with hot profile count.
+; So %dup should be duplicated into predecessors.
+define i32 @hot(i32 %a, i32* %p, i32* %q) !prof !22 {
+; CHECK-LABEL: hot
+; CHECK:       %entry
+; CHECK:       %true1
+; CHECK:       %false2
+; CHECK:       %false1
+; CHECK:       %true2
+entry:
+  %cond1 = icmp sgt i32 %a, 1
+  br i1 %cond1, label %true1, label %false1, !prof !30
+
+true1:
+  %v1 = load i32, i32* %p, align 4
+  %v2 = add i32 %v1, 2
+  br label %dup
+
+false1:
+  %v3 = load i32, i32* %q, align 4
+  %v4 = sub i32 %v3, 3
+  br label %dup
+
+dup:
+  %v5 = phi i32 [%v2, %true1], [%v4, %false1]
+  %cond2 = icmp sgt i32 %v5, 4
+  br i1 %cond2, label %true2, label %false2, !prof !30
+
+true2:
+  %v6 = xor i32 %v5, %a
+  br label %exit
+
+false2:
+  %v7 = and i32 %v5, %a
+  br label %exit
+
+exit:
+  %v8 = phi i32 [%v6, %true2], [%v7, %false2]
+  ret i32 %v8
+}
+
+
+!llvm.module.flags = !{!1}
+!21 = !{!"function_entry_count", i64 10}
+!22 = !{!"function_entry_count", i64 400}
+
+!30 = !{!"branch_weights", i32 1, i32 1}
+
+!1 = !{i32 1, !"ProfileSummary", !2}
+!2 = !{!3, !4, !5, !6, !7, !8, !9, !10}
+!3 = !{!"ProfileFormat", !"InstrProf"}
+!4 = !{!"TotalCount", i64 10000}
+!5 = !{!"MaxCount", i64 10}
+!6 = !{!"MaxInternalCount", i64 1}
+!7 = !{!"MaxFunctionCount", i64 1000}
+!8 = !{!"NumCounts", i64 3}
+!9 = !{!"NumFunctions", i64 3}
+!10 = !{!"DetailedSummary", !11}
+!11 = !{!12, !13, !14}
+!12 = !{i32 10000, i64 100, i32 1}
+!13 = !{i32 999000, i64 100, i32 1}
+!14 = !{i32 999999, i64 1, i32 2}