[MBP] Comments cleanup /NFC

[SjoerdMeijer]

Summary

Clean up of the comments, and a first attempt to better describe a part of the algorithm.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

616

yes, it should be freq(BB->Succ) which is the same as freq(S->BB)

620

This paragraph can be changed to:

if we have profile data (i.e, branch probabilities can be trusted), the cost (number of taken branches) with layout S->BB->Succ->Pred is 2 * freq(S->Pred) while the cost of topo order is freq(S->Pred) + freq(S->BB). We know Prob(S->BB) > Prob(S->Pred), so freq(S->BB) > freq(S->Pred), which means the cost of topological order is greater ...

[SjoerdMeijer]

Thanks for reviewing David. I have addressed your comments.

[davidxl]

lgtm

lib/CodeGen/MachineBlockPlacement.cpp

 static cl::opt<bool>
     ForcePreciseRotationCost("force-precise-rotation-cost",
                              cl::desc("Force the use of precise cost "
                                       "loop rotation strategy."),
                              cl::init(false), cl::Hidden);
 
 static cl::opt<unsigned> MisfetchCost(
     "misfetch-cost",
-    cl::desc("Cost that models the probablistic risk of an instruction "
+    cl::desc("Cost that models the probabilistic risk of an instruction "
              "misfetch due to a jump comparing to falling through, whose cost "
              "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);
 
class MachineBlockPlacement : public MachineFunctionPass {
   MachineBasicBlock *
   selectBestCandidateBlock(BlockChain &Chain,
                            SmallVectorImpl<MachineBasicBlock *> &WorkList);
   MachineBasicBlock *
   getFirstUnplacedBlock(const BlockChain &PlacedChain,
                         MachineFunction::iterator &PrevUnplacedBlockIt,
                         const BlockFilterSet *BlockFilter);
 
-  /// \brief Add a basic block to the work list if it is apropriate.
+  /// \brief Add a basic block to the work list if it is appropriate.
   ///
   /// If the optional parameter BlockFilter is provided, only MBB
   /// present in the set will be added to the worklist. If nullptr
   /// is provided, no filtering occurs.
   void fillWorkLists(MachineBasicBlock *MBB,
                      SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
                      const BlockFilterSet *BlockFilter);
   void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
BranchProbability MachineBlockPlacement::collectViableSuccessors(
   //     |  / \
   //     | B   C
   //     |  \ / \
   //     ----D   E
   //
   // Assume A->C is very hot (>90%), and C->D has a 50% probability, then after
   // A->C is chosen as a fall-through, D won't be selected as a successor of C
   // due to CFG constraint (the probability of C->D is not greater than
-  // HotProb to break top-oorder). If we exclude E that is not in BlockFilter
+  // HotProb to break top-order). If we exclude E that is not in BlockFilter
   // when calculating the  probability of C->D, D will be selected and we
   // will get A C D B as the layout of this loop.
   auto AdjustedSumProb = BranchProbability::getOne();
   for (MachineBasicBlock *Succ : BB->successors()) {
     bool SkipSucc = false;
     if (Succ->isEHPad() || (BlockFilter && !BlockFilter->count(Succ))) {
       SkipSucc = true;
     } else {
else
       Successors.push_back(Succ);
   }
 
   return AdjustedSumProb;
 }
 
 /// The helper function returns the branch probability that is adjusted
 /// or normalized over the new total \p AdjustedSumProb.
-
 static BranchProbability
 getAdjustedProbability(BranchProbability OrigProb,
                        BranchProbability AdjustedSumProb) {
   BranchProbability SuccProb;
   uint32_t SuccProbN = OrigProb.getNumerator();
   uint32_t SuccProbD = AdjustedSumProb.getNumerator();
   if (SuccProbN >= SuccProbD)
     SuccProb = BranchProbability::getOne();
   else
     SuccProb = BranchProbability(SuccProbN, SuccProbD);
 
   return SuccProb;
 }
 
 /// When the option OutlineOptionalBranches is on, this method
 /// checks if the fallthrough candidate block \p Succ (of block
 /// \p BB) also has other unscheduled predecessor blocks which
-/// are also successors of \p BB (forming triagular shape CFG).
+/// are also successors of \p BB (forming triangular shape CFG).
 /// If none of such predecessors are small, it returns true.
 /// The caller can choose to select \p Succ as the layout successors
 /// so that \p Succ's predecessors (optional branches) can be
 /// outlined.
 /// FIXME: fold this with more general layout cost analysis.
 bool MachineBlockPlacement::shouldPredBlockBeOutlined(
     MachineBasicBlock *BB, MachineBasicBlock *Succ, BlockChain &Chain,
     const BlockFilterSet *BlockFilter, BranchProbability SuccProb,

 
 /// 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) {
 
-  // This is no global conflict, just return false.
+  // There isn't a better layout when there are no unscheduled predecessors.
   if (SuccChain.UnscheduledPredecessors == 0)
     return false;
 
   // There are two basic scenarios here:
   // -------------------------------------
-  // Case 1: triagular shape CFG:
+  // Case 1: triangular shape CFG (if-then):
   //     BB
   //     | \
   //     |  \
   //     |   Pred
   //     |   /
   //     Succ
   // In this case, we are evaluating whether to select edge -> Succ, e.g.
   // set Succ as the layout successor of BB. Picking Succ as BB's
-  // successor breaks the  CFG constraints. With this layout, Pred BB
+  // successor breaks the CFG constraints (FIXME: define these constraints).
+  // With this layout, Pred BB
   // is forced to be outlined, so the overall cost will be cost of the
   // branch taken from BB to Pred, plus the cost of back taken branch
-  // from Pred to Succ, as well as the additional cost asssociated
+  // from Pred to Succ, as well as the additional cost associated
   // with the needed unconditional jump instruction from Pred To Succ.
+
   // The cost of the topological order layout is the taken branch cost
   // from BB to Succ, so to make BB->Succ a viable candidate, the following
   // must hold:
   //     2 * freq(BB->Pred) * taken_branch_cost + unconditional_jump_cost
   //      < freq(BB->Succ) *  taken_branch_cost.
   // Ignoring unconditional jump cost, we get
   //    freq(BB->Succ) > 2 * freq(BB->Pred), i.e.,
   //    prob(BB->Succ) > 2 * prob(BB->Pred)
   //
-  // When real profile data is available, we can precisely compute the the
-  // probabililty threshold that is needed for edge BB->Succ to be considered.
-  // With out profile data, the heuristic requires the branch bias to be
+  // When real profile data is available, we can precisely compute the
+  // probability threshold that is needed for edge BB->Succ to be considered.
+  // Without profile data, the heuristic requires the branch bias to be
   // a lot larger to make sure the signal is very strong (e.g. 80% default).
   // -----------------------------------------------------------------
-  // Case 2: diamond like CFG:
+  // Case 2: diamond like CFG (if-then-else):
   //     S
   //    / \
   //   |   \
   //  BB    Pred
   //   \    /
   //    Succ
   //    ..
-  // In this case, edge S->BB has already been selected, and we are evaluating
-  // candidate edge BB->Succ. Edge S->BB is selected because prob(S->BB)
-  // is no less than prob(S->Pred). When real profile data is *available*, if
-  // the condition is true, it will be always better to continue the trace with
-  // edge BB->Succ instead of laying out with topological order (i.e. laying
-  // Pred first).  The cost of S->BB->Succ is 2 * freq (S->Pred), while with
-  // the topo order, the cost is freq(S-> Pred) + Pred(S->BB) which is larger.
+  //
+  // The current block is BB and edge BB->Succ is now being evaluated.
+  // Note that edge S->BB was previously already selected because
+  // prob(S->BB) > prob(S->Pred).
+  // At this point, 2 blocks can be placed after BB: Pred or Succ. If we
+  // choose Pred, we will have a topological ordering as shown on the left
+  // in the picture below. If we choose Succ, we have the solution as shown
+  // on the right:
+  //
+  //   topo-order:
+  //
+  //       S-----                             ---S
+  //       |    |                             |  |
+  //    ---BB   |                             |  BB
+  //    |       |                             |  |
+  //    |  pred--                             |  Succ--
+  //    |  |                                  |       |
+  //    ---succ                               ---pred--
+  //
+  // cost = freq(S->Pred) + freq(BB->Succ)    cost = 2 * freq (S->Pred)
+  //      = freq(S->Pred) + freq(S->BB)
+  //
+  // If we have profile data (i.e, branch probabilities can be trusted), the
+  // cost (number of taken branches) with layout S->BB->Succ->Pred is 2 *
+  // freq(S->Pred) while the cost of topo order is freq(S->Pred) + freq(S->BB).
+  // We know Prob(S->BB) > Prob(S->Pred), so freq(S->BB) > freq(S->Pred), which
+  // means the cost of topological order is greater.
   // 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
+  // strong biased branch at block S with Prob(S->BB) in order to select
+  // BB->Succ. This is equivalent 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(BB);
 
   // Forward checking. For case 2, SuccProb will be 1.
   if (SuccProb < HotProb) {
     DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> " << SuccProb
for (MachineBasicBlock *Pred : Succ->predecessors()) {
     // Do backward checking. For case 1, it is actually redundant check. For
     // case 2 above, we need a backward checking to filter out edges that are
     // not 'strongly' biased. With profile data available, the check is mostly
     // redundant too (when threshold prob is set at 50%) unless S has more than
     // two successors.
     // BB  Pred
     //  \ /
     //  Succ
-    // We select edgee BB->Succ if
+    // We select edge BB->Succ if
     //      freq(BB->Succ) > freq(Succ) * HotProb
     //      i.e. freq(BB->Succ) > freq(BB->Succ) * HotProb + freq(Pred->Succ) *
     //      HotProb
     //      i.e. freq((BB->Succ) * (1 - HotProb) > freq(Pred->Succ) * HotProb
     BlockFrequency PredEdgeFreq =
         MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ);
     if (PredEdgeFreq * HotProb >= CandidateEdgeFreq * HotProb.getCompl()) {
       BadCFGConflict = true;

 
 /// \brief Select the best block from a worklist.
 ///
 /// This looks through the provided worklist as a list of candidate basic
 /// blocks and select the most profitable one to place. The definition of
 /// profitable only really makes sense in the context of a loop. This returns
 /// the most frequently visited block in the worklist, which in the case of
 /// a loop, is the one most desirable to be physically close to the rest of the
-/// loop body in order to improve icache behavior.
+/// loop body in order to improve i-cache behavior.
 ///
 /// \returns The best block found, or null if none are viable.
 MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock(
     BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList) {
   // Once we need to walk the worklist looking for a candidate, cleanup the
   // worklist of already placed entries.
   // FIXME: If this shows up on profiles, it could be folded (at the cost of
   // some code complexity) into the loop below.
MachineBlockPlacement::findBestLoopExit(MachineLoop &L,
   BlockChain &HeaderChain = *BlockToChain[L.getHeader()];
   if (!LoopBlockSet.count(*HeaderChain.begin()))
     return nullptr;
 
   BlockFrequency BestExitEdgeFreq;
   unsigned BestExitLoopDepth = 0;
   MachineBasicBlock *ExitingBB = nullptr;
   // If there are exits to outer loops, loop rotation can severely limit
-  // fallthrough opportunites unless it selects such an exit. Keep a set of
+  // fallthrough opportunities unless it selects such an exit. Keep a set of
   // blocks where rotating to exit with that block will reach an outer loop.
   SmallPtrSet<MachineBasicBlock *, 4> BlocksExitingToOuterLoop;
 
   DEBUG(dbgs() << "Finding best loop exit for: " << getBlockName(L.getHeader())
                << "\n");
   for (MachineBasicBlock *MBB : L.getBlocks()) {
     BlockChain &Chain = *BlockToChain[MBB];
     // Ensure that this block is at the end of a chain; otherwise it could be
DEBUG({
     }
     assert(!BadLoop && "Detected problems with the placement of this loop.");
   });
 
   BlockWorkList.clear();
   EHPadWorkList.clear();
 }
 
-/// When OutlineOpitonalBranches is on, this method colects BBs that
+/// When OutlineOpitonalBranches is on, this method collects BBs that
 /// dominates all terminator blocks of the function \p F.
 void MachineBlockPlacement::collectMustExecuteBBs() {
   if (OutlineOptionalBranches) {
     // Find the nearest common dominator of all of F's terminators.
     MachineBasicBlock *Terminator = nullptr;
     for (MachineBasicBlock &MBB : *F) {
       if (MBB.succ_size() == 0) {
         if (Terminator == nullptr)
for (MachineBasicBlock *ChainBB : FunctionChain) {
 
     // FIXME: It would be awesome of updateTerminator would just return rather
     // than assert when the branch cannot be analyzed in order to remove this
     // boiler plate.
     Cond.clear();
     MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
 
     // The "PrevBB" is not yet updated to reflect current code layout, so,
-    //   o. it may fall-through to a block without explict "goto" instruction
+    //   o. it may fall-through to a block without explicit "goto" instruction
     //      before layout, and no longer fall-through it after layout; or
     //   o. just opposite.
     //
     // AnalyzeBranch() may return erroneous value for FBB when these two
     // situations take place. For the first scenario FBB is mistakenly set NULL;
     // for the 2nd scenario, the FBB, which is expected to be NULL, is
     // mistakenly pointing to "*BI".
     // Thus, if the future change needs to use FBB before the layout is set, it
bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
   MDT = &getAnalysis<MachineDominatorTree>();
   assert(BlockToChain.empty());
 
   buildCFGChains();
 
   // Changing the layout can create new tail merging opportunities.
   TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
   // TailMerge can create jump into if branches that make CFG irreducible for
-  // HW that requires structurized CFG.
+  // HW that requires structured CFG.
   bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
                          PassConfig->getEnableTailMerge() &&
                          BranchFoldPlacement;
   // No tail merging opportunities if the block number is less than four.
   if (MF.size() > 3 && EnableTailMerge) {
     BranchFolder BF(/*EnableTailMerge=*/true, /*CommonHoist=*/false, *MBFI,
                     *MBPI);