[CodeGen] Do the Simple Early Return in block-placement pass to optimize the blocks

Summary:

Fix a bug of not update the jump table and recommit it again.

In `block-placement` pass, it will create some patterns for unconditional we can do the simple early retrun.
But the `early-ret` pass is before `block-placement`, we don't want to run it again.
This patch is to do the simple early return to optimize the blocks at the last of `block-placement`.

Reviewed By: efriedma

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

llvm-svn: 371177

1 files changed, 46 insertions, 0 deletions

diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
index f2a64faab2e..c9441bd80c1 100644
--- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
@@ -38,6 +38,7 @@
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachinePostDominators.h"
@@ -2712,6 +2713,7 @@ void MachineBlockPlacement::optimizeBranches() {
   // cannot because all branches may not be analyzable.
   // E.g., the target may be able to remove an unconditional branch to
   // a fallthrough when it occurs after predicated terminators.
+  SmallVector<MachineBasicBlock*, 4> EmptyBB;
   for (MachineBasicBlock *ChainBB : FunctionChain) {
     Cond.clear();
     MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
@@ -2731,9 +2733,50 @@ void MachineBlockPlacement::optimizeBranches() {
         TII->removeBranch(*ChainBB);
         TII->insertBranch(*ChainBB, FBB, TBB, Cond, dl);
         ChainBB->updateTerminator();
+      } else if (Cond.empty() && TBB && ChainBB != TBB && !TBB->empty() &&
+                 !TBB->canFallThrough()) {
+        // When ChainBB is unconditional branch to the TBB, and TBB has no
+        // fallthrough predecessor and fallthrough successor, try to merge
+        // ChainBB and TBB. This is legal under the one of following conditions:
+        // 1. ChainBB is empty except for an unconditional branch.
+        // 2. TBB has only one predecessor.
+        MachineFunction::iterator I(TBB);
+        if (((TBB == &*F->begin()) || !std::prev(I)->canFallThrough()) &&
+             (TailDup.isSimpleBB(ChainBB) || (TBB->pred_size() == 1))) {
+          TII->removeBranch(*ChainBB);
+          ChainBB->removeSuccessor(TBB);
+
+          // Update the CFG.
+          while (!TBB->pred_empty()) {
+            MachineBasicBlock *Pred = *(TBB->pred_end() - 1);
+            Pred->ReplaceUsesOfBlockWith(TBB, ChainBB);
+          }
+
+          while (!TBB->succ_empty()) {
+            MachineBasicBlock *Succ = *(TBB->succ_end() - 1);
+            ChainBB->addSuccessor(Succ, MBPI->getEdgeProbability(TBB, Succ));
+            TBB->removeSuccessor(Succ);
+          }
+
+          // Move all the instructions of TBB to ChainBB.
+          ChainBB->splice(ChainBB->end(), TBB, TBB->begin(), TBB->end());
+          EmptyBB.push_back(TBB);
+
+          // If TBB was the target of a jump table, update jump tables to go to
+          // the ChainBB instead.
+          if (MachineJumpTableInfo *MJTI = F->getJumpTableInfo())
+            MJTI->ReplaceMBBInJumpTables(TBB, ChainBB);
+        }
       }
     }
   }
+
+  for (auto BB: EmptyBB) {
+    MLI->removeBlock(BB);
+    FunctionChain.remove(BB);
+    BlockToChain.erase(BB);
+    F->erase(BB);
+  }
 }
 
 void MachineBlockPlacement::alignBlocks() {
@@ -3053,6 +3096,9 @@ bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
     }
   }
 
+  // optimizeBranches() may change the blocks, but we haven't updated the
+  // post-dominator tree. Because the post-dominator tree won't be used after
+  // this function and this pass don't preserve the post-dominator tree.
   optimizeBranches();
   alignBlocks();