Revive http://reviews.llvm.org/D12778 to handle forward-hot-prob and backward-hot-prob consistently.

[danielcdh]

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]

this makes sense.

lgtm.

lib/CodeGen/MachineBlockPlacement.cpp

if (SuccChain.UnscheduledPredecessors != 0) {
         DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> " << SuccProb
                      << " (prob) (CFG conflict)\n");
         continue;
       }
 
       // Make sure that a hot successor doesn't have a globally more
       // important predecessor.
       auto RealSuccProb = MBPI->getEdgeProbability(BB, Succ);
-      BlockFrequency CandidateEdgeFreq =
-          MBFI->getBlockFreq(BB) * RealSuccProb * HotProb.getCompl();
+      BlockFrequency CandidateEdgeFreq = MBFI->getBlockFreq(BB) * RealSuccProb;
       bool BadCFGConflict = false;
       for (MachineBasicBlock *Pred : Succ->predecessors()) {
         if (Pred == Succ || BlockToChain[Pred] == &SuccChain ||
             (BlockFilter && !BlockFilter->count(Pred)) ||
             BlockToChain[Pred] == &Chain)
           continue;
         BlockFrequency PredEdgeFreq =
             MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ);
-        if (PredEdgeFreq >= CandidateEdgeFreq) {
+        // A   B
+        //  \ /
+        //   C
+        // We layout ACB iff  A.freq > C.freq * HotProb
+        //               i.e. A.freq > A.freq * HotProb + B.freq * HotProb
+        //               i.e. A.freq * (1 - HotProb) > B.freq * HotProb
+        // A: CandidateEdge
+        // B: PredEdge
+        if (PredEdgeFreq * HotProb >= CandidateEdgeFreq * HotProb.getCompl()) {
           BadCFGConflict = true;
           break;
         }
       }
       if (BadCFGConflict) {
         DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> " << SuccProb
                      << " (prob) (non-cold CFG conflict)\n");
         continue;

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

outercleanup:
   %4 = phi { i8*, i32 } [%2, %innercleanup], [%3, %outerlp]
   call void @clean()
   resume { i8*, i32 } %4
 
 innercleanup:
   call void @clean()
   br label %outercleanup
 }
+
+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 !5
+
+then:
+  call void @hot_function()
+  br label %exit
+
+else:
+  call void @cold_function()
+  br label %exit
+
+exit:
+  call void @hot_function()
+  ret void
+}
+
+!5 = !{!"branch_weights", i32 84, i32 16}