[MBP] Factor out function hasViableTopFallthrough and enhancement

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.

Differential Revision: https://reviews.llvm.org/D58393

llvm-svn: 354682

2 files changed, 89 insertions, 9 deletions

diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
index a246717cad6..265aeabc15e 100644
--- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
@@ -453,6 +453,8 @@ class MachineBlockPlacement : public MachineFunctionPass {
                   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(
@@ -1984,6 +1986,39 @@ MachineBlockPlacement::findBestLoopExit(const MachineLoop &L,
   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
@@ -2003,15 +2038,7 @@ void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain,
   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
diff --git a/llvm/test/CodeGen/X86/bb_rotate.ll b/llvm/test/CodeGen/X86/bb_rotate.ll
new file mode 100644
index 00000000000..55a7b013802
--- /dev/null
+++ b/llvm/test/CodeGen/X86/bb_rotate.ll
@@ -0,0 +1,53 @@
+; 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}