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

hot-->likely

125

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

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

This condition does not look correct.

481

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

511–512

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

526

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.

lib/CodeGen/MachineBlockPlacement.cpp

cl::desc("Cost that models the probablistic risk of an instruction "
              "is zero."),
     cl::init(1), cl::Hidden);
 
 static cl::opt<unsigned> JumpInstCost("jump-inst-cost",
                                       cl::desc("Cost of jump instructions."),
                                       cl::init(1), 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 {
 /// \brief A chain of blocks which will be laid out contiguously.
 ///
 /// This is the datastructure representing a chain of consecutive blocks that
 /// are profitable to layout together in order to maximize fallthrough
 /// probabilities and code locality. We also can use a block chain to represent

 /// 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(StaticLikelyProb, 100);
+  const BranchProbability HotProb(
+      BB->getParent()->getFunction()->getEntryCount() ? ProfileLikelyProb
+                                                      : StaticLikelyProb,
+      100);
 
   MachineBasicBlock *BestSucc = nullptr;
   auto BestProb = BranchProbability::getZero();
 
   // Adjust edge probabilities by excluding edges pointing to blocks that is
   // either not in BlockFilter or is already in the current chain. Consider the
   // following CFG:
   //
else
       Successors.push_back(Succ);
   }
 
   DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n");
   for (MachineBasicBlock *Succ : Successors) {
     BranchProbability SuccProb;
     uint32_t SuccProbN = MBPI->getEdgeProbability(BB, Succ).getNumerator();
     uint32_t SuccProbD = AdjustedSumProb.getNumerator();
+
+    // When evaluating cost for the following CFG:
+    //  A
+    //  | \
+    //  |  B
+    //  | /
+    //  C
+    // Assume that the only cost is the taken jump instruction
+    // The cost of layout ABC = P(AC)
+    // The cost of layout ACB = P(AB) * 2
+    // We compare P(AB)*2 with P(AC) to find the best successor of A.
+    if (Successors.size() == 2) {
+      MachineBasicBlock *OtherSucc = NULL;
+      for (MachineBasicBlock *S : Successors)
+        if (S != Succ) {
+          OtherSucc = S;
+          break;
+        }
+      if (Succ->succ_size() == 1 && *Succ->succ_begin() == OtherSucc)
+        SuccProbN *= 2;
+    }
+
     if (SuccProbN >= SuccProbD)
       SuccProb = BranchProbability::getOne();
     else
       SuccProb = BranchProbability(SuccProbN, SuccProbD);
 
     // If we outline optional branches, look whether Succ is unavoidable, i.e.
     // dominates all terminators of the MachineFunction. If it does, other
     // successors must be optional. Don't do this for cold branches.
if (OutlineOptionalBranches && SuccProb > HotProb.getCompl() &&
           if (Pred->size() < OutlineOptionalThreshold)
             return true;
         }
         return false;
       };
       if (!HasShortOptionalBranch())
         return Succ;
     }
 
     // Only consider successors which are either "hot", or wouldn't violate
     // any CFG constraints.
     BlockChain &SuccChain = *BlockToChain[Succ];
     if (SuccChain.UnscheduledPredecessors != 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.
       auto RealSuccProb = MBPI->getEdgeProbability(BB, Succ);
       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);
         // A   B

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);