[MBP] Make sure the exit BB is the most possible successor before rotating a loop

[Carrot]

Summary

In findBestLoopExit it only finds a BB that can exit a loop, but it doesn't consider the exit BB may have other better predecessor. In that case the exit BB is placed after other predecessor, rotation actually makes loop layout worse.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1871

loop rotation can save one internal fall through, not just adding a loop exit fall through. Do you need to consider the overall cost/savings?

[Carrot]

lib/CodeGen/MachineBlockPlacement.cpp

1871

If MBB is not the best predecessor of Succ, then Succ will not be placed after MBB, the overall cost saving should not consider MBB -> Succ.

lib/CodeGen/MachineBlockPlacement.cpp

#endif
   void buildChain(const MachineBasicBlock *BB, BlockChain &Chain,
                   BlockFilterSet *BlockFilter = nullptr);
   bool canMoveBottomBlockToTop(const MachineBasicBlock *BottomBlock,
                                const MachineBasicBlock *OldTop);
   bool hasViableTopFallthrough(const MachineBasicBlock *Top,
                                const BlockFilterSet &LoopBlockSet);
   MachineBasicBlock *findBestLoopTop(
       const MachineLoop &L, const BlockFilterSet &LoopBlockSet);
+  bool isBestPred(const MachineBasicBlock *Succ, const MachineBasicBlock *MBB);
   MachineBasicBlock *findBestLoopExit(
       const MachineLoop &L, const BlockFilterSet &LoopBlockSet);
   BlockFilterSet collectLoopBlockSet(const MachineLoop &L);
   void buildLoopChains(const MachineLoop &L);
   void rotateLoop(
       BlockChain &LoopChain, const MachineBasicBlock *ExitingBB,
       const BlockFilterSet &LoopBlockSet);
   void rotateLoopWithProfile(
while (BestPred->pred_size() == 1 &&
          (*BestPred->pred_begin())->succ_size() == 1 &&
          *BestPred->pred_begin() != L.getHeader())
     BestPred = *BestPred->pred_begin();
 
   LLVM_DEBUG(dbgs() << "    final top: " << getBlockName(BestPred) << "\n");
   return BestPred;
 }
 
+/// Check if MBB is the best predecessor of block Succ.
+bool
+MachineBlockPlacement::isBestPred(const MachineBasicBlock *Succ,
+                                  const MachineBasicBlock *MBB) {
+  auto Prob = MBPI->getEdgeProbability(MBB, Succ);
+  BlockFrequency MaxFreq = MBFI->getBlockFreq(MBB) * Prob;
+
+  for (MachineBasicBlock *Pred : Succ->predecessors()) {
+    BlockChain *PredChain = BlockToChain[Pred];
+    // Pred can be placed before Succ if Pred is not in any chain,
+    // or it is at the end of some chain.
+    if (!PredChain || Pred == *std::prev(PredChain->end())) {
+      Prob = MBPI->getEdgeProbability(Pred, Succ);
+      BlockFrequency EdgeFreq = MBFI->getBlockFreq(Pred) * Prob;
+      if (EdgeFreq > MaxFreq)
+        return false;
+    }
+  }
+  return true;
+}
+
 /// Find the best loop exiting block for layout.
 ///
 /// This routine implements the logic to analyze the loop looking for the best
-/// block to layout at the top of the loop. Typically this is done to maximize
-/// fallthrough opportunities.
+/// block to layout at the bottom of the loop. Typically this is done to
+/// maximize fallthrough opportunities.
 MachineBasicBlock *
 MachineBlockPlacement::findBestLoopExit(const MachineLoop &L,
                                         const BlockFilterSet &LoopBlockSet) {
   // We don't want to layout the loop linearly in all cases. If the loop header
   // is just a normal basic block in the loop, we want to look for what block
   // within the loop is the best one to layout at the top. However, if the loop
   // header has be pre-merged into a chain due to predecessors not having
   // analyzable branches, *and* the predecessor it is merged with is *not* part
for (MachineBasicBlock *Succ : MBB->successors()) {
 
       unsigned SuccLoopDepth = 0;
       if (MachineLoop *ExitLoop = MLI->getLoopFor(Succ)) {
         SuccLoopDepth = ExitLoop->getLoopDepth();
         if (ExitLoop->contains(&L))
           BlocksExitingToOuterLoop.insert(MBB);
       }
 
+      if (!isBestPred(Succ, MBB))
+        continue;
+
       BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb;
       LLVM_DEBUG(dbgs() << "    exiting: " << getBlockName(MBB) << " -> "
                         << getBlockName(Succ) << " [L:" << SuccLoopDepth
                         << "] (";
                  MBFI->printBlockFreq(dbgs(), ExitEdgeFreq) << ")\n");
       // Note that we bias this toward an existing layout successor to retain
       // incoming order in the absence of better information. The exit must have
       // a frequency higher than the current exit before we consider breaking

test/CodeGen/X86/bb_rotate.ll

.exit:
   %val8 = call i1 @foo()
   br label %.stop
 
 .stop:
   %result = call i1 @foo()
   ret i1 %result
 }
 
+; Function @no_rotate is same as @no_viable_top_fallthrough. The only difference
+; is profile, so the block %.exit should be placed after %.bb1 instead of
+; rotating the loop.
+define i1 @no_rotate() {
+; CHECK-LABEL: no_rotate
+; CHECK: %.entry
+; CHECK: %.bb1
+; CHECK: %.exit
+; CHECK: %.stop
+; CHECK: %.header
+; CHECK: %.bb2
+; CHECK: %.middle
+; CHECK: %.backedge
+; CHECK: %.bb3
+.entry:
+  %val1 = call i1 @foo()
+  br i1 %val1, label %.bb1, label %.header, !prof !10
+
+.bb1:
+  %val2 = call i1 @foo()
+  br i1 %val2, label %.stop, label %.exit, !prof !11
+
+.header:
+  %val3 = call i1 @foo()
+  br i1 %val3, label %.bb2, label %.exit
+
+.bb2:
+  %val4 = call i1 @foo()
+  br i1 %val4, label %.middle, label %.bb3, !prof !10
+
+.middle:
+  %val5 = call i1 @foo()
+  br i1 %val5, label %.header, label %.backedge
+
+.backedge:
+  %val6 = call i1 @foo()
+  br label %.header
+
+.bb3:
+  %val7 = call i1 @foo()
+  br label %.middle
+
+.exit:
+  %val8 = call i1 @foo()
+  br label %.stop
+
+.stop:
+  %result = call i1 @foo()
+  ret i1 %result
+}
+
 declare i1 @foo()
 
 !10 = !{!"branch_weights", i32 90, i32 10}
+!11 = !{!"branch_weights", i32 10, i32 90}