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

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.

Reviewers: djasper, davidxl

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D20989

llvm-svn: 272203

1 files changed, 10 insertions, 3 deletions

diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
index c562af9d964..2900fef7a55 100644
--- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
@@ -496,8 +496,7 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
       // 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 ||
@@ -506,7 +505,15 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
           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;
         }