Change the probability to check if a hot successor has a more important predecessor in block-placement.

[congh]

Summary

Consider the following diamond CFG:

 A
/ \
B C
 \/
 D

Suppose A->B and A->C have probabilities 81% and 19%. In block-placement, A->B is called a hot edge and the final placement should be ABDC. However, the current implementation outputs ABCD. This is because when choosing the next block of B, it checks if Freq(C->D) > Freq(B->D) * 20%, which is true (if Freq(A) = 100, then Freq(B->D) = 81, Freq(C->D) = 19, and 19 > 81*20%=16.2). Actually, we should use 25% instead of 20% as the probability here, so that we have 19 < 81*25%=20.25, and the desired ABDC layout will be generated.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

354

This value should be tuned when PGO is on to follow a clear cost model. I would like to see a separate patch for that.

422

For global conflict detection, do we know why we need to apply the multiplier on the successor edge frequency and then compare with the conflicting incoming edge in the first place?

[congh]

Ping?

[congh]

lib/CodeGen/MachineBlockPlacement.cpp

354

The patch is ready but I am waiting for this patch being approved firstly.

422

At this point the decision whether to break CFG constraint is made. Considering the diamond branch I gave in the description and assume the probabilities are 60% and 40% respectively (for B and C). After B is chosen, we now decide whether to layout the other branch C. If we don't apply the multiplier here, we can see 40% < 60% and we may choose the D instead of C, which is not right (as we are using 80% as the threshold).

[djasper]

lib/CodeGen/MachineBlockPlacement.cpp

422

I think we should not hard code dependent values here. The 1/4 is strictly dependent on HotProb. So either pull out the denominator of HotProb into a variable or calculate this directly. I think you might need to replace

HotProb.getCompl()

with

HotProb.getCompl() / HotProb

But I am still jetlagged, so my math might be off.

[congh]

lib/CodeGen/MachineBlockPlacement.cpp

422

You are right. Before we use fixed point represented branch probability, it is a little tricky to do this as we don't have / operator defined for branch probability. Now for fixed point representation, we can just build the cold probability using numerators.

[congh]

Update the patch according to Daniel's comment.

[congh]

Ping?

[davidxl]

I will have another round of review in a couple of days ..

David

[davidxl]

While the fix seems reasonable, in reality without profile data (or with statically predicted branch probabilities), the effect of this change will be hard to predict.

On the other hand, I think we should do a better job in computing the branch costs and locality cost when profile data is available and does not rely on this magic 80/20 ratio.

lib/CodeGen/MachineBlockPlacement.cpp

 /// 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%
 
   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.
+      //
+      // We need to make sure a hot successor will be chosen, which has at least
+      // 80% probability. Considering a diamond CFG, and suppose two branches
+      // have 80% and 20% probabilities respectively. The ratio between
+      // probabilities of the cold edge and hot edge is 20/80, which is 25%.
+      // This is why we use 25% instead of 20% as the cold probability below.
+      assert(HotProb.getDenominator() == HotProb.getCompl().getDenominator());
+      const BranchProbability ColdProb(HotProb.getCompl().getNumerator(),
+                                       HotProb.getNumerator());
       BlockFrequency CandidateEdgeFreq =
-          MBFI->getBlockFreq(BB) * SuccProb * HotProb.getCompl();
+          MBFI->getBlockFreq(BB) * SuccProb * ColdProb;
       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) {

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:

test/CodeGen/X86/block-placement.ll

else:
   %gep2 = getelementptr i32, i32* %a, i32 2
   %val2 = load i32, i32* %gep2
   br label %exit
 
 exit:
   %ret = phi i32 [ %val1, %then ], [ %val2, %else ]
   ret i32 %ret
 }
+
+declare void @hot_function()
+
+define void @test_hot_branch(i32* %a) {
+; Test that a hot branch that has a probability a little larger than 80% will
+; break CFG constrains when doing block placement.
+; CHECK-LABEL: test_hot_branch:
+; CHECK: %entry
+; CHECK: %then
+; CHECK: %exit
+; CHECK: %else
+
+entry:
+  %gep1 = getelementptr i32, i32* %a, i32 1
+  %val1 = load i32, i32* %gep1
+  %cond1 = icmp ugt i32 %val1, 1
+  br i1 %cond1, label %then, label %else, !prof !3
+
+then:
+  call void @hot_function()
+  br label %exit
+
+else:
+  call void @cold_function()
+  br label %exit
+
+exit:
+  call void @hot_function()
+  ret void
+}
+
+!3 = !{!"branch_weights", i32 84, i32 16}