Set machine block placement hot prob threshold for both static and runtime profile.

[danielcdh]

Summary

With runtime profile, we have more confidence in branch probability, thus during basic block layout, we set a lower hot prob threshold so that blocks can be layouted optimally.

[davidxl]

The PGO related change is only half correct. In fact the trace successor probability threshold should be computed based on existing parameters misfetch cost and jump instruction cost.

In a diamond shaped CFG, the resulting succProb threshold is indeed 50% as the CFG is symmetric. For Triagular shaped CFG, the result will be very different because breaking topological order introduces more overhead compared with diamond shape case.

Given

   A
 /  |
B  |
  \ |
   C

If Prob(A,B) is greater than Prob(A,C), A B C should always be the right order. However, if if Prob(A,B) is lower than P(A,C), we need to compare the cost of A B C vs A C B

For A B C, the cost is

Prob(A,C) * Misfetch_cost due to the taken branch from A to C

For A C B, the cost is

Prob(A, B) *Misfetch_cost // taken branch from A to B

+ Prob(A,B) * misfetch_cost      // taken branch (unconditional) from B back to C
+ Prob(A,B) * jump_inst_cost    //  one more unconditional jump instruction is introduced

If jump instruction cost is assumed to be low (0), then Prob(A,C) needs to be >66% in order for A C B to be a better layout. If jump instr cost is the same as misfetch, we get 75% threshold.

We need to introduce a helper function to compute the threshold on the fly based on the CFG and parameter.

lib/CodeGen/MachineBlockPlacement.cpp

120 ↗

(On Diff #59634)

hot-->likely

125 ↗

(On Diff #59634)

hot --> likely

[danielcdh]

Handle the triangle-shape CFG.

[davidxl]

This function has gone bloated recently and needs some cleanups. I will first do a couple of NFC cleans so that it is in a form that is more friendly to inject cost based analysis first, you can then adapt your patch based on that.

lib/CodeGen/MachineBlockPlacement.cpp

472 ↗

(On Diff #60231)

It should look at the predecessors of the block C/'Succ' and find a Pred/B that is a candidate to be scheduled -- simliar to the confilct detection down below.

479 ↗

(On Diff #60231)

This condition does not look correct.

481 ↗

(On Diff #60231)

Should it adjust threshold BB instead?

[davidxl]

I've done refactoring/cleanup. I think the PGO logic can now be put into the new method: getLayoutSuccessorProbThreshold() -- the method needs to pass in BB and Succ. The implementation should be PGO specific.

Also please add a test case.

[danielcdh]

refactor

[danielcdh]

I'm still putting the triangle shape handling code outside as the logic is not related to PGO. Even with static profile, the triangle-shaped CFG should have a more relaxed condition to be topologically placed.

Added unittest to cover all cases.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

596 ↗

(On Diff #60727)

There is no need to pass this parameter -- MachineFunction is now a member field in the class.

621 ↗

(On Diff #60727)

It is probably not a good idea to bump the frequency of the alternate edge. Instead we should adjust the HotProb threshold computed by:

HotProb = getLayoutSuccessorProbThreshold(BB, Succ);

For instance

BB

\

Pred

/

SUcc

When Edge BB->Succ is examined, with PGO, the thresold should be adjusted to ~66% (compared to 50% default). In order words, in this shape, in order for BB->Succ to be considered, it needs at least 66% likely.

We should not change the non-PGO default (80%) now (can be done later -- but since it requires 'guessing' probbaility, a lot more perf testing is needed in order to change that)

[danielcdh]

handle triangle shape CFG only when profile is available.

[davidxl]

Please also add a case to cover topo-order with triaglar shape (with profile) as well as a diamond case where BP is ~60%.

lgtm.

llvm/trunk/lib/CodeGen/MachineBlockPlacement.cpp

 
 static cl::opt<bool>
 BranchFoldPlacement("branch-fold-placement",
               cl::desc("Perform branch folding during placement. "
                        "Reduces code size."),
               cl::init(true), cl::Hidden);
 
 extern cl::opt<unsigned> StaticLikelyProb;
+extern cl::opt<unsigned> ProfileLikelyProb;
 
 namespace {
 class BlockChain;
 /// \brief Type for our function-wide basic block -> block chain mapping.
 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
 }
 
 namespace {
for (MachineBasicBlock *Pred : Succ->predecessors()) {
       if (Pred->size() < OutlineOptionalThreshold)
         return false;
     }
     return true;
   } else
     return false;
 }
 
-// FIXME (PGO handling)
-// For now this method just returns a fixed threshold. It needs to be enhanced
-// such that BB and Succ is passed in so that CFG shapes are examined such that
-// the threshold is computed with more precise cost model when PGO is on.
-static BranchProbability getLayoutSuccessorProbThreshold() {
-  BranchProbability HotProb(StaticLikelyProb, 100);
-  return HotProb;
+// When profile is not present, return the StaticLikelyProb.
+// When profile is available, we need to handle the triangle-shape CFG.
+static BranchProbability getLayoutSuccessorProbThreshold(
+      MachineBasicBlock *BB) {
+  if (!BB->getParent()->getFunction()->getEntryCount())
+    return BranchProbability(StaticLikelyProb, 100);
+  if (BB->succ_size() == 2) {
+    const MachineBasicBlock *Succ1 = *BB->succ_begin();
+    const MachineBasicBlock *Succ2 = *(BB->succ_begin() + 1);
+    if (Succ1->isSuccessor(Succ2) || Succ2->isSuccessor(Succ1))
+      return BranchProbability(
+          200 - 2 * ProfileLikelyProb, 200 - ProfileLikelyProb);
+  }
+  return BranchProbability(ProfileLikelyProb, 100);
 }
 
 /// Checks to see if the layout candidate block \p Succ has a better layout
 /// predecessor than \c BB. If yes, returns true.
 bool MachineBlockPlacement::hasBetterLayoutPredecessor(
     MachineBasicBlock *BB, MachineBasicBlock *Succ, BlockChain &SuccChain,
     BranchProbability SuccProb, BranchProbability RealSuccProb,
     BlockChain &Chain, const BlockFilterSet *BlockFilter) {
bool MachineBlockPlacement::hasBetterLayoutPredecessor(
   // When profile data is not available, however, we need to be more
   // conservative. If the branch prediction is wrong, breaking the topo-order
   // will actually yield a layout with large cost. For this reason, we need
   // strong biaaed branch at block S with Prob(S->BB) in order to select
   // BB->Succ. This is equialant to looking the CFG backward with backward
   // edge: Prob(Succ->BB) needs to >= HotProb in order to be selected (without
   // profile data).
 
-  BranchProbability HotProb = getLayoutSuccessorProbThreshold();
+  BranchProbability HotProb = getLayoutSuccessorProbThreshold(BB);
 
   // Forward checking. For case 2, SuccProb will be 1.
   if (SuccProb < HotProb) {
     DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> " << SuccProb
                  << " (prob) (CFG conflict)\n");
     return true;
   }
 

llvm/trunk/lib/CodeGen/MachineBranchProbabilityInfo.cpp

 INITIALIZE_PASS_END(MachineBranchProbabilityInfo, "machine-branch-prob",
                     "Machine Branch Probability Analysis", false, true)
 
 cl::opt<unsigned> StaticLikelyProb(
     "static-likely-prob",
     cl::desc("branch probability threshold to be considered very likely"),
     cl::init(80), cl::Hidden);
 
+cl::opt<unsigned> ProfileLikelyProb(
+    "profile-likely-prob",
+    cl::desc("branch probability threshold to be considered very likely "
+             "when profile is available"),
+    cl::init(51), cl::Hidden);
+
 char MachineBranchProbabilityInfo::ID = 0;
 
 void MachineBranchProbabilityInfo::anchor() {}
 
 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
     const MachineBasicBlock *Src,
     MachineBasicBlock::const_succ_iterator Dst) const {
   return Src->getSuccProbability(Dst);

llvm/trunk/test/CodeGen/X86/block-placement.ll

else:
   call void @cold_function()
   br label %exit
 
 exit:
   call void @hot_function()
   ret void
 }
 
+define void @test_hot_branch_profile(i32* %a) !prof !6 {
+; Test that a hot branch that has a probability a little larger than 60% will
+; break CFG constrains when doing block placement when profile is available.
+; CHECK-LABEL: test_hot_branch_profile:
+; 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
+}
+
+define void @test_hot_branch_triangle_profile(i32* %a) !prof !6 {
+; Test that a hot branch that has a probability a little larger than 80% will
+; break triangle shaped CFG constrains when doing block placement if profile
+; is present.
+; CHECK-LABEL: test_hot_branch_triangle_profile:
+; CHECK: %entry
+; CHECK: %exit
+; CHECK: %then
+
+entry:
+  %gep1 = getelementptr i32, i32* %a, i32 1
+  %val1 = load i32, i32* %gep1
+  %cond1 = icmp ugt i32 %val1, 1
+  br i1 %cond1, label %exit, label %then, !prof !5
+
+then:
+  call void @hot_function()
+  br label %exit
+
+exit:
+  call void @hot_function()
+  ret void
+}
+
+define void @test_hot_branch_triangle_profile_topology(i32* %a) !prof !6 {
+; Test that a hot branch that has a probability between 50% and 66% will not
+; break triangle shaped CFG constrains when doing block placement if profile
+; is present.
+; CHECK-LABEL: test_hot_branch_triangle_profile_topology:
+; CHECK: %entry
+; CHECK: %then
+; CHECK: %exit
+
+entry:
+  %gep1 = getelementptr i32, i32* %a, i32 1
+  %val1 = load i32, i32* %gep1
+  %cond1 = icmp ugt i32 %val1, 1
+  br i1 %cond1, label %exit, label %then, !prof !7
+
+then:
+  call void @hot_function()
+  br label %exit
+
+exit:
+  call void @hot_function()
+  ret void
+}
+
 !5 = !{!"branch_weights", i32 84, i32 16}
+!6 = !{!"function_entry_count", i32 10}
+!7 = !{!"branch_weights", i32 60, i32 40}