[MBP] Factor out function hasViableTopFallthrough and enhancement

[Carrot]

Summary

This patch factor out the function hasViableTopFallthrough from rotateLoop. It is also enhanced. Original code checks only if there is a block can be placed before current loop top. This patch also checks if the loop top is the most possible successor of its predecessor. The attached test case shows its effect.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

2008

What is the purpose of the check 'Succ == *SuccChain->begin() ?

[Carrot]

lib/CodeGen/MachineBlockPlacement.cpp

2008

!SuccChain means Succ has not been layout in any chain.
'Succ == *SuccChain->begin()' means even Succ has been layout in some chain, the whole chain can still be layout after Pred if it is beneficial.
So (!SuccChain || Succ == *SuccChain->begin()) means it is possible to put Succ after Pred.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

2008

please add a comment there

[davidxl]

lgtm

lib/CodeGen/MachineBlockPlacement.cpp

#endif
   void fillWorkLists(const MachineBasicBlock *MBB,
                      SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
                      const BlockFilterSet *BlockFilter);
 
   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);
   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,
if (!BlocksExitingToOuterLoop.empty() &&
       !BlocksExitingToOuterLoop.count(ExitingBB))
     return nullptr;
 
   LLVM_DEBUG(dbgs() << "  Best exiting block: " << getBlockName(ExitingBB)
                     << "\n");
   return ExitingBB;
 }
 
+/// Check if there is a fallthrough to loop header Top.
+///
+///   1. Look for a Pred that can be layout before Top.
+///   2. Check if Top is the most possible successor of Pred.
+bool
+MachineBlockPlacement::hasViableTopFallthrough(
+    const MachineBasicBlock *Top,
+    const BlockFilterSet &LoopBlockSet) {
+  for (MachineBasicBlock *Pred : Top->predecessors()) {
+    BlockChain *PredChain = BlockToChain[Pred];
+    if (!LoopBlockSet.count(Pred) &&
+        (!PredChain || Pred == *std::prev(PredChain->end()))) {
+      // Found a Pred block can be placed before Top.
+      // Check if Top is the best successor of Pred.
+      auto TopProb = MBPI->getEdgeProbability(Pred, Top);
+      bool TopOK = true;
+      for (MachineBasicBlock *Succ : Pred->successors()) {
+        auto SuccProb = MBPI->getEdgeProbability(Pred, Succ);
+        BlockChain *SuccChain = BlockToChain[Succ];
+        // Check if Succ can be placed after Pred.
+        // Succ should not be in any chain, or it is the head of some chain.
+        if ((!SuccChain || Succ == *SuccChain->begin()) && SuccProb > TopProb) {
+          TopOK = false;
+          break;
+        }
+      }
+      if (TopOK)
+        return true;
+    }
+  }
+  return false;
+}
+
 /// Attempt to rotate an exiting block to the bottom of the loop.
 ///
 /// Once we have built a chain, try to rotate it to line up the hot exit block
 /// with fallthrough out of the loop if doing so doesn't introduce unnecessary
 /// branches. For example, if the loop has fallthrough into its header and out
 /// of its bottom already, don't rotate it.
 void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain,
                                        const MachineBasicBlock *ExitingBB,
                                        const BlockFilterSet &LoopBlockSet) {
   if (!ExitingBB)
     return;
 
   MachineBasicBlock *Top = *LoopChain.begin();
   MachineBasicBlock *Bottom = *std::prev(LoopChain.end());
 
   // If ExitingBB is already the last one in a chain then nothing to do.
   if (Bottom == ExitingBB)
     return;
 
-  bool ViableTopFallthrough = false;
-  for (MachineBasicBlock *Pred : Top->predecessors()) {
-    BlockChain *PredChain = BlockToChain[Pred];
-    if (!LoopBlockSet.count(Pred) &&
-        (!PredChain || Pred == *std::prev(PredChain->end()))) {
-      ViableTopFallthrough = true;
-      break;
-    }
-  }
+  bool ViableTopFallthrough = hasViableTopFallthrough(Top, LoopBlockSet);
 
   // If the header has viable fallthrough, check whether the current loop
   // bottom is a viable exiting block. If so, bail out as rotating will
   // introduce an unnecessary branch.
   if (ViableTopFallthrough) {
     for (MachineBasicBlock *Succ : Bottom->successors()) {
       BlockChain *SuccChain = BlockToChain[Succ];
       if (!LoopBlockSet.count(Succ) &&

test/CodeGen/X86/bb_rotate.ll

+; RUN: llc -mtriple=i686-linux < %s | FileCheck %s
+
+define i1 @no_viable_top_fallthrough() {
+; CHECK-LABEL: no_viable_top_fallthrough
+; CHECK: %.entry
+; CHECK: %.bb1
+; CHECK: %.bb2
+; CHECK: %.middle
+; CHECK: %.backedge
+; CHECK: %.bb3
+; CHECK: %.header
+; CHECK: %.exit
+; CHECK: %.stop
+.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 !10
+
+.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}