[MBP] Added some more debug messages and some clean ups /NFC

[SjoerdMeijer]

Summary

Added some more debug messages and some clean ups /NFC

[davidxl]

Otherwise looks good.

lib/CodeGen/MachineBlockPlacement.cpp

570

I suggest removing change in this paragraph -- it does not seem to make things clearer.

[SjoerdMeijer]

Ok, will remove that paragraph and then commit. Thanks for reviewing.

lib/CodeGen/MachineBlockPlacement.cpp

 
 // FIXME: Find a good default for this flag and remove the flag.
 static cl::opt<unsigned> ExitBlockBias(
     "block-placement-exit-block-bias",
     cl::desc("Block frequency percentage a loop exit block needs "
              "over the original exit to be considered the new exit."),
     cl::init(0), cl::Hidden);
 
+// Definition:
+// - Outlining: placement of a basic block outside the chain or hot path.
+
 static cl::opt<bool> OutlineOptionalBranches(
     "outline-optional-branches",
-    cl::desc("Put completely optional branches, i.e. branches with a common "
-             "post dominator, out of line."),
+    cl::desc("Outlining optional branches will place blocks that are optional "
+              "branches, i.e. branches with a common post dominator, outside "
+              "the hot path or chain"),
     cl::init(false), cl::Hidden);
 
 static cl::opt<unsigned> OutlineOptionalThreshold(
     "outline-optional-threshold",
     cl::desc("Don't outline optional branches that are a single block with an "
              "instruction count below this threshold"),
     cl::init(4), cl::Hidden);
 
bool MachineBlockPlacement::hasBetterLayoutPredecessor(
   // -------------------------------------
   // 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 (FIXME: define these constraints).
+  //
+  // Here, we are evaluating to select Succ or Pred as a successor of BB.
+  // If we choose Succ, then we break the topological ordering and Pred needs
+  // to be outlined which is shown here:
+  //
+  //                ---<----
+  //                |      |
+  //          BB-->Succ   Pred
+  //           |           |
+  //           ------>------
+  //
+  // The cost = taken_branch(BB->Pred) + taken_back_branch(Pred->Succ) +
+  //            uncond_branch(Pred->Succ)
+  //
   // 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 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)
bool MachineBlockPlacement::hasBetterLayoutPredecessor(
   // 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
-                 << " (prob) (CFG conflict)\n");
+    DEBUG(dbgs() << "    Not a candidate: " << getBlockName(Succ) << " "
+                 << "Respecting topological ordering because "
+                 << "probability is less than prob treshold: " 
+                 << SuccProb << "\n");
     return true;
   }
 
   // Make sure that a hot successor doesn't have a globally more
   // important predecessor.
   BlockFrequency CandidateEdgeFreq = MBFI->getBlockFreq(BB) * RealSuccProb;
   bool BadCFGConflict = false;
 
BlockFrequency PredEdgeFreq =
         MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ);
     if (PredEdgeFreq * HotProb >= CandidateEdgeFreq * HotProb.getCompl()) {
       BadCFGConflict = true;
       break;
     }
   }
 
   if (BadCFGConflict) {
-    DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> " << SuccProb
+    DEBUG(dbgs() << "    Not a candidate: " << getBlockName(Succ) << " -> " << SuccProb
                  << " (prob) (non-cold CFG conflict)\n");
     return true;
   }
 
   return false;
 }
 
 /// \brief Select the best successor for a block.
MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
 
   MachineBasicBlock *BestSucc = nullptr;
   auto BestProb = BranchProbability::getZero();
 
   SmallVector<MachineBasicBlock *, 4> Successors;
   auto AdjustedSumProb =
       collectViableSuccessors(BB, Chain, BlockFilter, Successors);
 
-  DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n");
+  DEBUG(dbgs() << "Selecting best successor for: " << getBlockName(BB) << "\n");
   for (MachineBasicBlock *Succ : Successors) {
     auto RealSuccProb = MBPI->getEdgeProbability(BB, Succ);
     BranchProbability SuccProb =
         getAdjustedProbability(RealSuccProb, AdjustedSumProb);
 
     // This heuristic is off by default.
     if (shouldPredBlockBeOutlined(BB, Succ, Chain, BlockFilter, SuccProb,
                                   HotProb))
       return Succ;
 
     BlockChain &SuccChain = *BlockToChain[Succ];
     // Skip the edge \c BB->Succ if block \c Succ has a better layout
     // predecessor that yields lower global cost.
     if (hasBetterLayoutPredecessor(BB, Succ, SuccChain, SuccProb, RealSuccProb,
                                    Chain, BlockFilter))
       continue;
 
     DEBUG(
-        dbgs() << "    " << getBlockName(Succ) << " -> " << SuccProb
-               << " (prob)"
+        dbgs() << "    Candidate: " << getBlockName(Succ) << ", probability: "
+               << SuccProb
                << (SuccChain.UnscheduledPredecessors != 0 ? " (CFG break)" : "")
                << "\n");
-    if (BestSucc && BestProb >= SuccProb)
+
+    if (BestSucc && BestProb >= SuccProb) {
+      DEBUG(dbgs() << "    Not the best candidate, continuing\n");
       continue;
+    }
+
+    DEBUG(dbgs() << "    Setting it as best candidate\n");
     BestSucc = Succ;
     BestProb = SuccProb;
   }
+  if (BestSucc)
+    DEBUG(dbgs() << "    Selected: " << getBlockName(BestSucc) << "\n");
+
   return BestSucc;
 }
 
 /// \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
MachineBlockPlacement::findBestLoopTop(MachineLoop &L,
   DEBUG(dbgs() << "Finding best loop top for: " << getBlockName(L.getHeader())
                << "\n");
 
   BlockFrequency BestPredFreq;
   MachineBasicBlock *BestPred = nullptr;
   for (MachineBasicBlock *Pred : L.getHeader()->predecessors()) {
     if (!LoopBlockSet.count(Pred))
       continue;
-    DEBUG(dbgs() << "    header pred: " << getBlockName(Pred) << ", "
+    DEBUG(dbgs() << "    header pred: " << getBlockName(Pred) << ", has "
                  << Pred->succ_size() << " successors, ";
           MBFI->printBlockFreq(dbgs(), Pred) << " freq\n");
     if (Pred->succ_size() > 1)
       continue;
 
     BlockFrequency PredFreq = MBFI->getBlockFreq(Pred);
     if (!BestPred || PredFreq > BestPredFreq ||
         (!(PredFreq < BestPredFreq) &&
for (MachineBasicBlock *MBB : L.getBlocks()) {
     if (!HasLoopingSucc) {
       // Restore the old exiting state, no viable looping successor was found.
       ExitingBB = OldExitingBB;
       BestExitEdgeFreq = OldBestExitEdgeFreq;
     }
   }
   // Without a candidate exiting block or with only a single block in the
   // loop, just use the loop header to layout the loop.
-  if (!ExitingBB || L.getNumBlocks() == 1)
+  if (!ExitingBB) {
+    DEBUG(dbgs() << "    No other candidate exit blocks, using loop header\n");
     return nullptr;
+  }
+  if (L.getNumBlocks() == 1) {
+    DEBUG(dbgs() << "    Loop has 1 block, using loop header as exit\n");
+    return nullptr;
+  }
 
   // Also, if we have exit blocks which lead to outer loops but didn't select
   // one of them as the exiting block we are rotating toward, disable loop
   // rotation altogether.
   if (!BlocksExitingToOuterLoop.empty() &&
       !BlocksExitingToOuterLoop.count(ExitingBB))
     return nullptr;